原问题:

假设您有1001 整数组。整数组按随机顺序排列,但您知道每个整数在1到1000之间(包含在内)。此外,除一个数字外,每个数字只在数组中出现一次,一个数字发生两次。

它基本上说, 算法只有在有连续整数, 以 1 < / 强 > 开始, 以一些 N 结尾时才有效 。

如果您想修改为更一般的个案,您必须做以下工作:

在数组中查找最小值和最大值。 然后计算预期输出( 最小值和最大值之间的 X 或全部整数) 。 然后计算数组中所有元素的 x 。 然后 x 将这两件事进行修改, 然后输入输出 。

记住 XOR 操作员的这两个特性 :

(1) 如果取0(0)的x或数字,该数字将再次返回同一数字。

意思, n = 0 = n

(2) 如果将一个数字的xor随身携带,则返回0(0)。

意思是, 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步:找出从“最小”到“最大”的所有整数的XOR(包括)。

步骤 3 : 查找给定数组所有元素的 XOR 。

步骤4:步骤2的XOR和步骤3将提供所需的重复编号。

说明:

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 )

XOR 语句的属性是 XOR a 将始终为 0, 也就是说它们会取消, 因此, 如果您知道您的列表只有一个重复, 而您的情况范围是 x 到 y, 601 到 607, 那么将所有元素的 x 保存在变量中是可行的, 然后将这个变量与您在数组中的所有元素一起 xor 。 因为将只有一个元素被重复, 它将不会因 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输出!

这是原始问题中显示的代码, 与您的执行不同。 您已经修改过它, 以便使用本地变量, 而不是数组中最后一个成员, 从而产生不同效果 :

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

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

//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 You can use HashTable and Hash Function when you enter the same
value into the hash table that time you can make count if its greater than
one value at particular index of HashTable then you can say that there are repeated value in the array.

XOR 基本上只有在您对数组进行了排序时才有效。 所以时间复杂性是 O( logn) 。

def duplicateNumber(arr):
    arr.sort()
    for i in range(1, len(arr)):
        if arr[i] ^ arr[i-1] == 0:
            return True
    return False

更好的方法

def duplicateDetect(arr):
    slow = arr[arr[0]]
    fast = arr[arr[arr[0]]]
    while slow != fast:
        slow = arr[slow]
        fast = arr[arr[fast]]
    fast = arr[0]
    while slow != fast:
        slow = arr[slow]
        fast = arr[fast]
    return slow

Time-Complexity - O(2*n) Space-Complexity - O(1)

使用Hashmap的另一种方法(工作取决于问题说明和问题所需的某些修改。 )

from collections import Counter
def duplicate(arr):
    c = colletions.Counter(arr)
    for key, val in c.items():
        if val == 2:
           return key