# 查找在数组中一次出现的元素，其中每个其他元素出现两次 > 原文： [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;     } ```