リスト内の単一の数値を見つける [重複]

https://stackoverflow.com/questions/35185

09-06-2019
|

質問

この質問にはすでに答えがあります:

配列内で 2 回出現しない唯一の数値を見つける方法 [重複] 5 つの答え

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

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

解決

最も高速 (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 からそれ自体のマークが解除されるためです。マークされていない唯一のものは、重複していないものです。

他のヒント

ちなみに、このアイデアを拡張すると、すぐに次のことを見つけることができます。二重複リストの中で一意の番号。

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

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

バム。

O(N) 時間、O(N) メモリ

HT= ハッシュテーブル

ht.clear（）あなたが見るアイテムごとにリストを調べます

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

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

注 (クレジット @Jared Updike):このシステムは、アイテムの奇数のインスタンスをすべて検索します。

コメント:NLogN のパフォーマンスを実現するソリューションにどうして人々が投票できるのかわかりません。どの宇宙でそれが「優れている」のでしょうか？あなたが受け入れられた回答の NLogN ソリューションにマークを付けたことにさらにショックを受けました...

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

カイルのソリューションでは、データセットがルールに従っていない状況を明らかに捕捉できません。すべての数値がペアになっている場合、アルゴリズムは結果としてゼロを返します。これは、ゼロが 1 回出現する唯一の値であるかのように、まったく同じ値です。

単一出現値またはトリプル値が複数ある場合も、結果はエラーになります。

データセットをテストすると、メモリまたは時間のどちらかでよりコストのかかるアルゴリズムが使用される可能性があります。

Csmba のソリューションでは、いくつかのエラーデータ (値が 0 つ以上発生するか) は表示されますが、その他 (4 つの値) は表示されません。彼の解決策に関しては、HT の実装に応じて、メモリおよび/または時間のいずれかが O(n) を超えます。

入力セットの正確性を確信できない場合は、ソートしてカウントするか、整数自体をハッシュキーとして出現回数をカウントするハッシュテーブルを使用することが可能です。

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

そして今、問題は「最良の」並べ替えアルゴリズムを見つけることです。並べ替えアルゴリズムは多数あり、それぞれに長所と短所があるため、これは非常に複雑な問題です。のウィキペディアの項目それに関する素晴らしい情報源のようです。

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

「最良」とは何を意味するのかを指定する必要があります。ある人にとっては、速度だけが重要であり、回答を「最良」とみなす人もいますが、他の人にとっては、ソリューションが読みやすければ数百ミリ秒を許容するかもしれません。

「最高」とは、より具体的にしない限り、主観的なものです。

それはこう言いました：

数値を繰り返し処理し、各数値についてリストでその数値を検索し、検索結果の数に対して 1 のみを返す数値に達したら完了です。

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

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

質問

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

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

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

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

衝突が見つかるまで、セット内の要素を単純にハッシュに入れることができます。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

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow