查找偶數次重複數組中的整數，其餘整數重複奇數次

Question

給定是一個整數數組。陣列中的每個數字都會出現奇數次，但只有1個數字出現偶數次。找到那個號碼。

下面是我在stackoverflow上讀取的解決方案不起作用。我無法找到該解決方案的鏈接，我想知道是否有人可以幫助我理解爲什麼這個解決方案不正確，除非我在下面做錯了什麼。

我們首先對數組中的所有元素進行異或運算。我們稱之爲aWithOutDuplicate，其中包含除重複之外的所有奇怪元素。然後我們或所有的元素。我們稱之爲aAllUnique，它應該包含所有的獨特元素。 XORing aWithOutDuplicate和aAllUnique應該吐出重複的元素。

int arr[] = {1,2,3,4,5,6,7,8,4,9}; 
    int aWithOutDuplicate = 0; 
    int aAllUnique = 0; 

    for(int i=0;i<arr.length;i++) { 
     aWithOutDuplicate ^= arr[i]; 
     aAllUnique |= arr[i]; 
    } 

    cout << (aWithOutDuplicate^aAllUnique); 

更新： 我不知道這個問題可以在O（n）時間和O（1）空間複雜度來解決。

Answer 1

這種方法不起作用，因爲沒有辦法區分偶數次出現的數字和從不出現的數字。考慮一下這個4位例如：

5: 1 0 1 
10: 0 1 0 1 
----------- 
    1 1 1 1 <- both or and xor. 

現在，任何號碼（< = 15，因爲它是4位）添加到列表兩次。或者將保持不變，因爲所有的位已經打開，對於x的所有4位值，0xf | x == 0xf。 xor將保持不變，因爲所有x的值都是0xf^x^x == 0xf。因此，您的方法的一個反例可能是，例如{5, 10, 1, 1}。

Answer 2

假設你有數組：a，b，a，b，a，c 所以輸出應該是b。 我會盡力解釋爲什麼你的算法是wronng。當您應用OR操作時，您會認爲您將獲得唯一的號碼。是的，當然，| | a | a == a，但通過執行以下操作可獲得什麼價值：a | b | c ==？ （可能所有的位都被設置爲1，取決於a，b，c） 這與XOR不同。

Answer 3

這爲O（n），O（1）空間解決方案適用ONLY如果數組元素是在範圍[1，N-1]爲大小 'n' 的陣列。 [將工作爲[0，N-1]與後述的幾個調整]

• 掃描陣列，並執行以下

  for(i=0; i < n; i++) 
      A[A[i]]=A[A[i]]*(-1) 
  

• 具有奇數出現的所有數組元素將具有掃描結束時爲負值。具有偶數次數的元素將具有正值。

幾個調整： 如果數組範圍是從[0，N-1]，可以在第一次通過期間以特殊字符具有「0」，其中替換的特殊情況「0」 （而不是否定）。您必須在第二階段回覆特殊字符回到'0'等等。

Answer 4

在下面的代碼，我發現這是重複偶數的時候，下面的暴力方法，而無需使用標準庫函數圖中的數字：

//! Print integers occurring an even number of times in array a. 

#include <iostream> 

int main() { 
    int arr[] = { 9, 12, 23, 10, 12, 12, 15, 23, 14, 12, 15 }; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int b[n], count = 0, c[100]; 

    for (int i = 0; i < n; i++) { 
     for (int j = 0; j < n; j++) 
      if (arr[j] == arr[i]) 
       b[i] = ++count; 
     count = 0; 
    } 
    for (int i = 0; i < n; i++) 
     c[arr[i]] = 0; 
    for (int i = 0; i < n; i++) { 
     if (c[arr[i]] == 1) 
      continue; 
     if (b[i] % 2 == 0) 
      std::cout << arr[i] << std::endl; 
     c[arr[i]]++; 
    } 
    return 0; 
}