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

30

请记住 XOR 运算符的这两个属性：

(1) 如果你对一个数字与 0 ( zero ) 进行异或，它会再次返回相同的数字。

意味着 , n ^ 0 = n

(2) 如果你对一个数字本身进行异或，它将返回 0（零）。

意味着 , n ^ n = 0

现在，问题来了：

   Let    Input_arr = { 23 , 21 , 24 , 27 , 22 , 27 , 26 , 25 }    

   Output should be 27 ( because 27 is the duplicate element in the Input_arr ).

解决方案 ：

第 1 步：在给定数组中找到“min”和“max”值。这将需要 O(n)。

第 2 步：查找从“min”到“max”（包括）范围内的所有整数的 XOR。

第 3 步：查找给定数组的所有元素的 XOR。

第 4 步：第 2 步和第 3 步的 XOR 将给出所需的重复编号。

描述 ：

Step1 : min = 21 , max = 27

Step 2 : Step2_result = 21 ^ 22 ^ 23 ^ 24 ^ 25 ^ 26 ^ 27 = 20

Step 3 : Step3_result = 23 ^ 21 ^ 24 ^ 27 ^ 22 ^ 27 ^ 26 ^ 25 = 15

Step 4 : Final_Result = Step2_result ^ Step3_result = 20 ^ 15 = 27

But , How Final_Result calculated the duplicate number ?

Final_Result = ( 21 ^ 22 ^ 23 ^ 24 ^ 25 ^ 26 ^ 27 ) ^ ( 23 ^ 21 ^ 24 ^ 27 ^ 22 ^ 27 ^ 26 ^ 25 )

Now , Remember above two properties : n ^ n = 0 AND n ^ 0 = n

So , here ,

Final_Result = ( 21 ^ 21 ) ^ ( 22 ^ 22 ) ^ ( 23 ^ 23 ) ^ ( 24 ^ 24 ) ^ ( 25 ^ 25 ) ^ ( 26 ^ 26 ) ^ ( 27 ^ 27 ^ 27 )

             = 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ ( 27 ^ 0 ) ( property applied )

             = 0 ^ 27 ( because we know 0 ^ 0 = 0 )

             = 27 ( Required Result )
于 2018-11-06T07:47:14.643 回答
25

从原始问题：

假设您有一个包含 1001 个整数的数组。整数是随机顺序的，但您知道每个整数都在 1 到 1000（含）之间。此外，每个数字在数组中只出现一次，除了一个数字出现两次。

它基本上说，该算法仅在您有连续整数时才有效，从 1 开始，以某个 N 结尾。

如果要将其修改为更一般的情况，则必须执行以下操作：

在数组中找到最小值和最大值。然后计算预期输出（异或最小值和最大值之间的所有整数）。然后计算数组中所有元素的异或。然后对这两件事进行异或，你会得到一个输出。

于 2012-05-26T08:47:51.683 回答
11

XOR 语句具有 'a' XOR 'a' 将始终为 0 的属性，即它们相互抵消，因此，如果您知道您的列表只有一个重复项并且范围是 x 到 y、601 到 607在您的情况下，可以将 x 到 y 的所有元素的异或保留在一个变量中，然后将该变量与数组中的所有元素异或。由于只有一个元素将被复制，因此不会因异或运算而被取消，这将是您的答案。

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 回答
2 
//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 当您
在哈希表中输入相同的值时，您可以使用哈希表和哈希函数，如果它在哈希表的特定索引处大于
一个值，则可以进行计数，那么您可以说数组中有重复的值。

于 2017-08-03T20:49:44.800 回答
1

尽管此处提供的答案很好，但如果有歧义，我希望您参考Mohit Jain的答案。

该事实variable xor variable = zero可用于精确且轻松地定位阵列中存在的重复项。希望有帮助！

于 2019-01-03T21:21:55.693 回答