10

投稿に出くわしましたシャッフルされた連続整数の配列で重複する要素を見つける方法? しかし、これは多くの入力で失敗することに後で気付きました。

例：
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;
}

すべてのケースで重複する要素が見つかるように、このコードを変更するにはどうすればよいですか?

4

6 に答える 6

25

元の質問から:

1001 個の整数の配列があるとします。整数はランダムな順序ですが、各整数が 1 から 1000 (両端を含む) の間であることがわかっています。さらに、2 回出現する 1 つの数値を除いて、各数値は配列内で 1 回だけ出現します。

基本的に、そのアルゴリズムは、 1で始まり N で終わる連続した整数がある場合にのみ機能します。

より一般的なケースに変更する場合は、次のことを行う必要があります。

配列内の最小値と最大値を見つけます。次に、期待される出力を計算します (最小値と最大値の間のすべての整数の xor)。次に、配列内のすべての要素の xor を計算します。次に、この 2 つのことを xor すると、出力が得られます。

于 2012-05-26T08:47:51.683 に答える
11

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 を提供します。

于 2012-05-26T13:41:55.640 に答える
3

元の質問に示されているコードは、実装とは異なります。配列の最後のメンバーの代わりにローカル変数を使用するように変更したため、違いが生じました。

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

printf("Answer : %d\n", array[1000]);
于 2012-05-26T08:06:13.737 に答える