# 在未排序的數組中找到出現奇數的兩個數字 > 原文： [https://www.geeksforgeeks.org/find-the-two-numbers-with-odd-occurences-in-an-unsorted-array/](https://www.geeksforgeeks.org/find-the-two-numbers-with-odd-occurences-in-an-unsorted-array/) 給定一個未排序的數組，其中包含除兩個數字以外的所有數字的偶數個出現次數。 找出在`O(n)`時間復雜度和`O(1)`額外空間中出現奇數的兩個數字。 例子： ``` Input: {12, 23, 34, 12, 12, 23, 12, 45} Output: 34 and 45 Input: {4, 4, 100, 5000, 4, 4, 4, 4, 100, 100} Output: 100 and 5000 Input: {10, 20} Output: 10 and 20 ``` 解決此問題的一種**樸素的方法**是運行兩個嵌套循環。 外循環拾取一個元素，內循環計數拾取的元素的出現次數。 如果出現次數是奇數，則打印數字。 該方法的時間復雜度為 O（n ^ 2）。 我們可以使用排序**來獲得 O（nLogn）時間中出現的奇數。 首先使用 O（nLogn）排序算法（例如合并排序，堆排序等）對數字進行排序。對數組進行排序后，我們要做的就是對數組進行線性掃描并打印出現的奇數。** 我們還可以**使用哈希**。 創建一個空的哈希表，其中將包含元素及其計數。 一一挑選輸入數組的所有元素。 在哈希表中查找選擇的元素。 如果在哈希表中找到該元素，則在表中增加其計數。 如果未找到該元素，則將其輸入到哈希表中，計數為 1。將所有元素輸入哈希表后，掃描哈希表并打印具有奇數的元素。 這種方法平均可能需要`O(n)`時間，但需要`O(n)`額外空間。 **`O(n)`時間和`O(1)`額外空間解決方案**： 這個想法類似于此帖子的[方法 2。 令兩個出現的奇數為 x 和 y。 我們**使用按位異或**獲得 x 和 y。 第一步是對數組中存在的所有元素進行 XOR。 由于 XOR 運算的以下特性，所有元素的 XOR 使我們對 x 和 y 進行 XOR。 1）任何數字 n 與自身的 XOR 給我們 0，即 n ^ n = 0 2）任何數字 n 與 0 的 XOR 給我們 n，即 n ^ 0 = n 3 ）XOR 是累積性和關聯性的。](https://www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/) 因此，第一步之后，我們對 x 和 y 進行了 XOR。 令 XOR 的值為 xor2。 xor2 中的每個置位指示 x 和 y 中的對應位具有彼此不同的值。 例如，如果 x = 6（0110）并且 y 為 15（1111），則 xor2 將為（1001），xor2 中的兩個置位指示 x 和 y 中的相應位不同。 在第二步中，我們選擇 xor2 的一個固定位并將數組元素分為兩組。 x 和 y 將進入不同的組。 在下面的代碼中，選擇 xor2 的最右邊設置位是因為很容易獲得數字的最右邊設置位。 如果我們對所有具有對應位集（或 1）的數組元素進行 XOR，則得到第一個奇數。 而且，如果我們對所有具有相應位 0 的元素進行 XOR，那么我們將獲得另一個奇數發生數。 由于 XOR 具有相同的屬性，因此可以執行此步驟。 一個數字的所有出現都將進入同一集合。 對所有出現的偶數次出現的所有數字進行 XOR 運算，其結果將為 0。 集合的異或將是奇數發生的元素之一。 ## C++ ```cpp // C++ Program to find the two odd occurring elements? #include <bits/stdc++.h> using namespace std; /* Prints two numbers that occur odd number of times. The? function assumes that the array size is at least 2 and? there are exactly two numbers occurring odd number of times. */ void printTwoOdd(int arr[], int size)? {? ????int xor2 = arr[0]; /* Will hold XOR of two odd occurring elements */ ????int set_bit_no; /* Will have only single set bit of xor2 */ ????int i;? ????int n = size - 2;? ????int x = 0, y = 0;? ????/* Get the xor of all elements in arr[]. The xor will basically? ????????be xor of two odd occurring elements */ ????for(i = 1; i < size; i++)? ????????xor2 = xor2 ^ arr[i];? ????/* Get one set bit in the xor2\. We get rightmost set bit? ????????in the following line as it is easy to get */ ????set_bit_no = xor2 & ~(xor2-1);? ????/* Now divide elements in two sets:? ????????1) The elements having the corresponding bit as 1.? ????????2) The elements having the corresponding bit as 0\. */ ????for(i = 0; i < size; i++)? ????{? ????????/* XOR of first set is finally going to hold one odd? ????????occurring number x */ ????????if(arr[i] & set_bit_no)? ????????x = x ^ arr[i];? ????????/* XOR of second set is finally going to hold the other? ????????odd occurring number y */ ????????else ????????y = y ^ arr[i];? ????}? ????cout << "The two ODD elements are " << x << " & " << y;? }? /* Driver code */ int main()? {? ????int arr[] = {4, 2, 4, 5, 2, 3, 3, 1};? ????int arr_size = sizeof(arr)/sizeof(arr[0]);? ????printTwoOdd(arr, arr_size);? ????return 0;? }? // This is code is contributed by rathbhupendra ```