algorithm - リスト内の単一の数字を見つける

Question

他のすべての数字が正確に 2 回出現するリストで、1 回だけ出現する数字を見つけるための最適なアルゴリズムは何でしょうか。

したがって、整数のリスト (配列として取りましょう) では、各整数が 1 回を除いて正確に 2 回繰り返されます。それを見つけるには、最適なアルゴリズムは何ですか。

Answer 1

最速 (O(n)) でメモリ効率が最も高い (O(1)) 方法は、XOR 操作を使用することです。

C:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

これは「1」を出力します。これは、1 回だけ発生するものです。

これが機能するのは、最初に数値をヒットすると num 変数がそれ自体でマークされ、2 回目には num がそれ自体でマーク解除されるためです (多かれ少なかれ)。マークされていない唯一のものは、重複していないものです。

Answer 2

ところで、このアイデアを拡張して、重複リストの中から2 つの一意の番号をすばやく見つけることができます。

一意の番号を a と b としましょう。カイルが提案したように、まずすべての XOR を取ります。得られるのは a^b です。a != b であるため、a^b != 0 であることがわかります。a^b の任意の 1 ビットを選択し、それをマスクとして使用します。より詳細には、x & (a^b) が非ゼロになるように x を 2 の累乗として選択します。

次に、リストを 2 つのサブリストに分割します。一方のサブリストにはすべての数値 y と y&x == 0 が含まれ、残りはもう一方のサブリストに入ります。x を選択したところで、a と b は異なるバケットにあることがわかります。また、重複の各ペアがまだ同じバケットにあることもわかっています。したがって、古い「XOR-em-all」トリックを各バケットに個別に適用し、a と b が何であるかを完全に発見できるようになりました。

バム。

Answer 3

O(N) 回、O(N) メモリ

HT= ハッシュ テーブル

HT.clear() 表示される項目ごとに順番にリストを調べます

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

最後に、HT 内のアイテムが探しているアイテムです。

注 (クレジット @Jared Updike): このシステムは、アイテムの Odd インスタンスをすべて見つけます。

---

コメント: NLogN のパフォーマンスを実現するソリューションに投票する方法がわかりません。どの宇宙でそれは「より良い」ですか? あなたが受け入れられた回答のNLogNソリューションをマークしたことにさらにショックを受けました...

ただし、メモリを一定にする必要がある場合は、NLogN が (これまでのところ) 最適なソリューションであることに同意します。

Answer 4

Kyle のソリューションは、データ セットがルールに従っていない場合、明らかに状況を把握できません。すべての数値がペアになっている場合、アルゴリズムはゼロの結果を返します。ゼロとまったく同じ値は、単一の出現を持つ唯一の値になります。

複数の単一オカレンス値またはトリプルが存在する場合、結果はエラーになります。

データセットをテストすると、メモリまたは時間のいずれかで、よりコストのかかるアルゴリズムになる可能性があります。

Csmba のソリューションは、一部のエラー データ (単一の発生値がないか、1 つ以上) を示しますが、他の (4 倍) は示しません。彼の解決策に関しては、HT の実装によっては、メモリや時間のいずれかが O(n) を超えています。

入力セットの正確性について確信が持てない場合は、ソートとカウント、または整数自体がハッシュキーであるハッシュテーブルのカウントオカレンスの使用の両方が実行可能です。

Answer 5

並べ替えアルゴリズムを使用し、並べ替えられたリストを調べて番号を見つけるのが良い方法だと思います。

そして今、問題は「最良の」ソートアルゴリズムを見つけることです。並べ替えアルゴリズムはたくさんあり、それぞれに長所と短所があるため、これは非常に複雑な質問です。ウィキペディアのエントリは、それに関する優れた情報源のようです。

Answer 6

Ruby での実装:

a = [1,2,3,4,123,1,2,.........]
t = a.length-1
for i in 0..t
   s = a.index(a[i])+1
   b = a[s..t]
   w = b.include?a[i]
   if w == false
       puts a[i]
   end
end

Answer 7

ソート法と XOR 法の時間計算量は同じです。2 つの文字列のビットごとの XOR が一定時間の操作であると仮定した場合、XOR メソッドは O(n) のみです。これは、配列内の整数のサイズが定数によって制限されていると言うことと同じです。その場合、基数ソートを使用して配列を O(n) でソートできます。

数値が制限されていない場合、ビットごとの XOR には O(k) の時間がかかります。ここで、k はビット文字列の長さであり、XOR メソッドには O(nk) かかります。ここでも、基数ソートは時間 O(nk) で配列をソートします。

Answer 8

ただし、数字がどれだけ大きい/小さいか/多様であるかによって異なります。基数ソートを適用すると、O(N log N) ソリューションのソート時間が大幅に短縮される場合があります。

Answer 9

「最高」とは何を意味するのかを指定する必要があります。一部の人にとっては、速度がすべてであり、答えを「最高」と見なす人もいます。他の人にとっては、ソリューションがより読みやすい場合、数百ミリ秒を許す可能性があります。

あなたがより具体的でない限り、「最高」は主観的です。

---

それは言った：

数字を反復処理し、数字ごとにその数字のリストを検索し、検索結果の数として 1 のみを返す数字に到達したら完了です。

Answer 10

あなたができる最善のことは、リストを反復処理することです。すべてのアイテムについて、「表示された」アイテムのリストに追加するか、すでに存在する場合は「表示された」から削除し、最後に「表示された」のリスト" 項目には単数形の要素が含まれます。これは、時間に関しては O(n) であり、スペースに関しては n です (最悪の場合、リストがソートされていれば、はるかに良くなります)。

それらが整数であるという事実は、実際には考慮されていません。それらを加算することでできる特別なことは何もないからです...ありますか?

質問

選択された回答がどの基準でも「最良」である理由がわかりません。O(N*lgN) > O(N) であり、リストを変更します (または、そのコピーを作成しますが、これはスペースと時間の点でさらに高価です)。何か不足していますか？

Answer 11

衝突が見つかるまで、セット内の要素を単純にハッシュに入れることができます。Ruby では、これはワンライナーです。

def find_dupe(array)
  h={}
  array.detect { |e| h[e]||(h[e]=true; false) }
end

したがって、find_dupe([1,2,3,4,5,1])1 が返されます。

ただし、これは実際には一般的な「トリック」インタビューの質問です。これは通常、1 つの重複がある連続した整数のリストに関するものです。この場合、インタビュアーは、実際の合計から減算するなど、 n整数のガウス合計を使用するようにあなたを求めていることがよくあります。n*(n+1)/2教科書の答えはこのようなものです。

def find_dupe_for_consecutive_integers(array)
  n=array.size-1   # subtract one from array.size because of the dupe
  array.sum - n*(n+1)/2
end