查找給定數組中的2個重複元素

Question

給定一個具有n+2元素的數組，陣列中的所有元素都在1至n的範圍內，並且除兩個出現兩次的元素外，所有元素只出現一次。

查找這2個重複數字。例如，如果陣列是[4, 2, 4, 5, 2, 3, 1]，然後n是5，有n+2 = 7元素與存在的只有一次除2和4

所有元素所以我的問題是如何使用XOR操作，以解決上述問題。我在其他網站上看到了解決方案，但我無法理解它。請考慮下面的例子：

arr[] = {2, 4, 7, 9, 2, 4}

1. XOR每一個元素。 xor = 2^4^7^9^2^4 = 14（1110）
2. 優惠數目僅具有一個異或的設置位。由於我們可以輕鬆獲得最右邊的一組，所以讓我們使用它。
3. set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010。現在set_bit_no將只設置爲xor的最右邊的設置位。
4. 現在分在兩組中的元素，做每一組元素的XOR，我們得到的非重複元素7和9

Answer 1

是的，你可以用異或解決它。這個答案擴大到Paulo Almeida's great comment。

該算法的工作方式如下：

由於我們知道數組包含每一個元素在範圍[1 ... N]，我們開始由陣列中的每個元素進行XOR在一起，然後異或與每一個結果元素的範圍[1 .. n]。由於XOR屬性，唯一元素被抵消，結果是重複元素的XOR（因爲重複元素總共進行了3次XOR，而其他所有元素都進行了XORed兩次並取消）。這存儲在xor_dups。

接下來，找到xor_dups中的一位，即1。再次，由於XOR的屬性，xor_dups中的位設置爲1意味着該位在重複數字的二進制表示中不同。任何1位都可以用於下一步，我的實現選擇最不重要。這存儲在diff_bit。

現在，將數組元素分成兩組：一組包含在我們從xor_dups中挑選的1位位置上具有0位的數字。另一個組包含具有1位的數字。由於這一點與我們所尋找的數字不同，它們不能同時在同一組中。此外，每個號碼的兩次出現都轉到同一組。我們現在差不多完成了。考慮具有0位元素的組。將它們全部XOR，然後將結果與範圍[1..n]中的那個位置上具有0位的所有元素進行異或運算，結果是該組的重複號碼（因爲在內部只有一個數字重複每個組，所有未重複的數字都被取消，因爲除了重複的XOR數據三次之外，每個數據都被異或）。

沖洗，重複：用於與所述1位的基團，異或它們放在一起，然後用在[1的範圍內的所有元素的異或結果..n]，該位置上有1位，結果是另一個重複號碼。

這裏的C中的實現：

#include <assert.h> 

void find_two_repeating(int arr[], size_t arr_len, int *a, int *b) { 
    assert(arr_len > 3); 
    size_t n = arr_len-2; 
    int i; 

    int xor_dups = 0; 
    for (i = 0; i < arr_len; i++) 
     xor_dups ^= arr[i]; 
    for (i = 1; i <= n; i++) 
     xor_dups ^= i; 

    int diff_bit = xor_dups & -xor_dups; 
    *a = 0; 
    *b = 0; 

    for (i = 0; i < arr_len; i++) 
     if (arr[i] & diff_bit) 
      *a ^= arr[i]; 
     else 
      *b ^= arr[i]; 

    for (i = 1; i <= n; i++) 
     if (i & diff_bit) 
      *a ^= i; 
     else 
      *b ^= i; 
} 

arr_len是陣列arr（的n+2的值）的總長度，並省略重複條目存儲在*a和*b（這些所謂的輸出參數）。