線性時間，恆定空間算法，用於查找在列表中出現1次的元素

Question

給定一個n個整數的列表，其中列表中的每個整數都存在兩次，除了一個元素在列表中存在一次。例如，

[1 3 3 6 2 7 1 2 7] 

我需要找到一個線性時間爲O（n），和恆定的空間O（1）算法，該算法返回其在列表中存在一次的元素。在上面的例子中，該算法應該返回6. 請注意，該列表不是由任何特定順序提供的。 （列表中元素的順序是隨機的）。

我可以使用字典在O（n）線性時間內解決這個問題，但不幸的是字典需要O（n）空間。有任何想法嗎？

Answer 1

解決這個難題需要知識的一個小訣竅：XOR-自己的數字偶數次導致零。此外，你可以在XOR之間的其他數字與臨時結果;順序無關緊要。

因此，如果您XOR陣列中的所有值加在一起，你會得到所存在的數組只有一次的唯一號碼是：

int res = 0; 
for (int i = 0 ; i != array.size() ; i++) { 
    res ^= array[i]; 
} 
cout << res << endl; 

Answer 2

您可以在列表中異或所有的數字一起。結果將是不重複的元素。