剑指OFFER-数组中只出现一次的数字

QuestionSolutionsort + pop异或

Question

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 关键词：数组 次数 异或

Solution

看到这题就想起那个只出现一次的字符。不过这题已知条件更多一点，至少我们知道会有两个出现一次的数字，而且其他数字成双成对出现。

sort + pop

第一反应当然是排序啦（N·log(N)），然后利用栈，进去相同就弹出，最后剩下俩数字。 时间复杂度：O(N·log(N) + N) 空间复杂度：O(1)

Python class Solution: # 返回[a,b] 其中ab是出现一次的两个数字 def FindNumsAppearOnce(self, array): array.sort() ans = [] for a in array: if not ans or a!=ans[-1]: ans.append(a) elif a == ans[-1]: ans.pop() return ans C++ class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { vector<int> ans; sort(data.begin(), data.end()); for(int i=0; i<data.size(); i++){ if(ans.empty() || data[i] != ans.back()) ans.push_back(data[i]); else ans.pop_back(); } *num1 = ans[0]; *num2 = ans[1]; return; } };

异或

然后神奇的教科书还有一种解法，达到了理论上最小的复杂度(N)，那就是利用异或的特性: 交换律：A ^ B = B ^ A 其他：A ^ A = 0， A ^ 0 = A

1）假设数组是[a, c, d, b, d, c]，对所有数字异或，根据交换律a ^ c ^ d ^ b ^ d ^ c = a ^ b ^ (c ^ c ^ d ^ d) = a ^ b ^ 0 = a ^ b。

2）现在我们得到一个k = a ^ b，k中如果某位为0代表a和b该位相同，如果为1代表a和b该位不相同。我们找一个k中为1的任何一位作为标志（这里我们用第一个为1的位s），因为a、b在这一位不同，那么他们一个是0，一个是1。我们把s位是1的数字分为一组，剩下是0的作为另外一组。这两组中分别包含a、b以及其他的相同数字。假设第一组是[a, c, c, …]，重复第一步方法，将这个数组全部异或，我们可以得到a ^ (c ^ c ^ …) = a，同理b ^ (d ^ d ^ …) = b

时间复杂度：O(N) 空间复杂度：O(1)

Python class Solution: # 返回[a,b] 其中ab是出现一次的两个数字 def FindNumsAppearOnce(self, array): c = 0 for n in array: c = c ^ n index = 1 while index & c == 0: index = index << 1 a, b = 0, 0 for n in array: if index & n == 0: a = a ^ n else: b = b ^ n return [a, b] C++ class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { int c = 0; for(int i = 0; i < data.size(); i++) c = c ^ data[i]; int index = 1; while((index & c) == 0) index = index << 1; int a= 0, b = 0; for(int i = 0; i < data.size(); i++){ if((index & data[i]) == 0) a = a ^ data[i]; else b = b ^ data[i]; } *num1 = a; *num2 = b; return; } };