3

配列内の重複を見つける方法。すべての一意の要素を見つける必要がある逆問題の場合、すべての要素を xor するだけで、結果として一意の要素が得られます。たとえば、

int a[] = {2, 2, 3, 3, 4, 5, 5, 16, 16};
int res = a[0];
for(int i = 0; i < 9; ++i)
    res ^= a[i];

たとえば、与えられた配列

int a[] = {2, 4, 7, 8, 4, 5};

ここでは重複は 4 ですが、配列の重複要素を見つける方法が明確ではありません。

4

3 に答える 3

4

Element Distinctness Problemについて説明しています。

余分なスペース (およびハッシュ) がなければO(n)、要素の明確性の問題を解決できないため、この問題の「重複の xor アルゴリズム」を変更することはできません。

この問題の解決策は次のとおりです。

  1. ソートされた配列をソートして繰り返し、重複を見つけます（ソートされた配列では簡単です）。これがO(nlogn)時間です。
  2. データのヒストグラム(ハッシュベース) を作成し、完了したらヒストグラムを繰り返して、ヒストグラムですべての要素の値が 1 であるかどうかを確認します -O(n) 平均的なケース、O(n) スペース。
于 2013-07-27T15:07:16.160 に答える
0

次のアルゴリズムを使用すると、配列内の重複を 0(n) 時間で見つけることができます。

  traverse the list for i= 0 to n-1 elements
  {
//check for sign of A[abs(A[i])] ;
 if positive then
 make it negative by   A[abs(A[i])]=-A[abs(A[i])];
 else  // i.e., A[abs(A[i])] is negative
  this   element (ith element of list) is a repetition
  }

それが役に立てば幸い！

于 2014-09-29T01:02:03.967 に答える
-1

1 つの解決策は、ハッシュセットを構築することです。それは次のようになります-

 1. Initialize an empty hashset.
 2. For each element in array,
     a. Check if it is present in the hashset.
        If yes, you found the duplicate
        If not, add it to the hashset.

このようにして、配列内のすべての重複を見つけることができます。

スペースの複雑さ: O(n) ; 時間の複雑さ: O(n)

于 2013-09-29T06:11:05.617 に答える