整数を含む配列があります。この配列で k 回繰り返される数字を見つけたいと思います。配列はソートされておらず、数値は制限されていません。
例、
A(20, 6, 99, 3, 6, 2, 1,11,41, 31, 99, 6, 7, 8, 99, 10, 99, ,6)
3回以上繰り返される数字を見つけてください。
答え: 6,99
ビットごとの操作 (xor) または組み合わせを使用して可能な答え? 実行時間の効率 Big(o) は、スペース容量だけでなく必要です。
これは宿題ではなく、単に興味深い問題です。
Patrick87 はおそらくコメントで最も簡単な答えを持っているので、別のアプローチを示します。
リストを反復処理すると、要素 (id、値) の作成とマップへの挿入の両方が行われます。ここで、id は数値に相当し、値は挿入時に 1 に初期化されたカウントと一致します。値がマップに既に存在する場合は、カウンターをインクリメントするだけです。
マップへの挿入には O(log k) 時間かかります。ここで、k はマップのサイズです。したがって、マップの合計作成時間は O(n log n) です。
マップが作成された後、マップを反復処理して、カウント == ターゲット カウントとなる任意の数値を出力できます。
時間の複雑さ = O(n) + O(n log n) + O(n) = O(n log n) 空間の複雑さ = O(n) + O(n) = O(n)
より良いスペースの複雑さを探している場合、それを取得することはできません...数値がストリームから読み取られた場合でも、O(n) である個々の値を追跡する必要があります。