配列内の重複要素を見つけるためにXOR演算子を使用すると多くの場合失敗する

Question

投稿How to find a duplicate element in an array of shuffled consecutive integers?が出てきましたが、後でこれが多くの入力で失敗することがわかりました。 EXのために

：重複した要素はすべてのケースのために見つけることができるように
arr[] = {601,602,603,604,605,605,606,607}

#include <stdio.h> 
int main() 
{ 
int arr[] = {2,3,4,5,5,7}; 
int i, dupe = 0; 
for (i = 0; i < 6; i++) { 
    dupe = dupe^a[i]^i; 
} 
printf ("%d\n", dupe); 
return 0; 
} 

どのように私はこのコードを変更することができますか？

Answer 1

：あなたは違いがローカル変数の代わりに、配列の最後のメンバーを、使用するように変更した

あなたは1001個の整数の配列を持っていると仮定します。整数はランダムな順序ですが、各整数が1〜1000（整数を含む）であることがわかります。さらに、1つの数字を除いて、各数字はアレイに1回だけ表示されます。これは2回発生します。

それは基本的には連続した整数を持っている場合、そのアルゴリズムは唯一あなたがより一般的な場合に、それを変更したい場合は、あなたがしなければならないは、いくつかのN.

で終わる、1から始まる、働く、と言います以下のもの：

配列内の最小値と最大値を探します。次に期待出力を計算する（xorまたは最小と最大の間のすべての整数）。次に、arrayのすべての要素のxorを計算します。そして、この2つのことをxorまたはあなたは出力を取得します。

Answer 2

元の質問に表示されているコードは、実装とは異なります。元の質問から

for (int i = 1; i < 1001; i++) 
{ 
    array[i] = array[i]^array[i-1]^i; 
} 

printf("Answer : %d\n", array[1000]); 

Answer 3

XORステートメントには、 'a' XOR 'a'は常に0になるというプロパティがあります。つまり、リストには重複が1つしかなく、範囲がxからy 、601〜607の場合は、xとyの間のすべての要素のxorを変数に保存し、配列内のすべての要素でこの変数をxorにすることが可能です。複製される要素は1つだけなので、xor操作のためにキャンセルされず、それがあなたの答えになります。

void main() 
{ 
    int a[8]={601,602,603,604,605,605,606,607}; 
    int k,i,j=601; 

    for(i=602;i<=607;i++) 
    { 
     j=j^i; 
    } 

    for(k=0;k<8;k++) 
    { 
     j=j^a[k]; 
    } 

    printf("%d",j); 
} 

このコードは、出力605を必要に応じて出力します。あなたはハッシュテーブルにハッシュテーブルの特定のインデックスで、そのより大きい
つの値、その後場合は、カウントを作ることができる時間を同じ
値を入力するとき

Answer 4

//There i have created the program to find out the duplicate element in array. Please edit if there are required some changes. 
int main() 
{ 
    int arr[] = {601,602,603,604,605,605,606,607}; 
    //int arr[] = {601,601,604,602,605,606,607}; 
    int n= sizeof(arr)/sizeof(arr[0]); 

    for (int i = 0; i < n; i++) 
    { 
     for (int j = i+1; j < n; j++) 
     { 
      int res = arr[i]^arr[j]; 

      if (res == 0) 
      { 
       std::cout<< "Repeated Element in array = "<<arr[i]<<std::endl; 
      } 
     } 
    } 
    return 0; 
} 

// ORあなたはハッシュテーブルとハッシュ関数を使用することができます配列に繰り返し値があると言うことができます。