# 查找在數組中一次出現的元素，其中每個其他元素出現兩次 > 原文： [http://quiz.geeksforgeeks.org/find-the-element-that-appears-once/](http://quiz.geeksforgeeks.org/find-the-element-that-appears-once/) 給定一個整數數組。 除了一個數字出現一次以外，所有數字出現兩次。 在`O(n)`時間&恒定的額外空間中找到數字。 **示例**： ``` Input: ar[] = {7, 3, 5, 4, 5, 3, 4} Output: 7 ``` 一種解決方案是檢查每個元素是否出現一次。 一旦找到一個元素，將其返回。 該解決方案的時間復雜度為 `O(n^2)`。 更好的解決方案是使用哈希。 1）遍歷所有元素并將它們放在哈希表中。 元素用作鍵，出現次數用作哈希表中的值。 2）再次遍歷數組，并在哈希表中打印計數為 1 的元素。 此解決方案可以在`O(n)`的時間內工作，但需要額外的空間。 最好的解決方案是使用 XOR。 所有數組元素的 XOR 運算使我們得到一次出現的數字。 該想法基于以下兩個事實。 a）一個數字與它自身的 XOR 為 0。 b）一個數字與 0 自身的 XOR 為數字本身。 ``` Let us consider the above example. Let ^ be xor operator as in C and C++. res = 7 ^ 3 ^ 5 ^ 4 ^ 5 ^ 3 ^ 4 Since XOR is associative and commutative, above expression can be written as: res = 7 ^ (3 ^ 3) ^ (4 ^ 4) ^ (5 ^ 5) = 7 ^ 0 ^ 0 ^ 0 = 7 ^ 0 = 7 ``` 以下是上述算法的實現。 ## C++ ```cpp // C++ program to find the array? // element that appears only once #include <iostream> using namespace std; int findSingle(int ar[], int ar_size) ????{ ????????// Do XOR of all elements and return ????????int res = ar[0]; ????????for (int i = 1; i < ar_size; i++) ????????????res = res ^ ar[i]; ????????return res; ????} // Driver code int main() ????{ ????????int ar[] = {2, 3, 5, 4, 5, 3, 4}; ????????int n = sizeof(ar) / sizeof(ar[0]); ????????cout << "Element occurring once is "? ?????????????<< findSingle(ar, n); ????????return 0; ????} ```