题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
分析：首先考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。这个题目的突破口在哪里？题目为什么要强调有一个数字出现一次，其他的出现两次？想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。
有了上面简单问题的解决方案之后，回到原始的问题。如果能够把原数组分为两个子数组，在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办法就是分别求出这两个只出现一次的数字了。
还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。在结果数字中找到第一个为1的位的位置，记为第N位。现在以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。
现在已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。因此到此为止，所有的问题都已经解决。
#include <iostream> using namespace std; // Find the index of first bit which is 1 in num (assuming not 0) unsigned int FindFirstBitIs1(int num) { int indexBit = 0; while (((num & 1) == 0) && (indexBit < 32)) { num = num >> 1; ++ indexBit; } return indexBit; } // Is the indexBit bit of num 1? bool IsBit1(int num, unsigned int indexBit) { num = num >> indexBit; return (num & 1); } // Find two numbers which only appear once in an array // Input: data - an array contains two number appearing exactly once, void FindNumsAppearOnce(int data[], int length, int &num1, int &num2) { if (length < 2) return; // get num1 ^ num2 int resultExclusiveOR = 0; for (int i = 0; i < length; ++ i) resultExclusiveOR ^= data[i]; // get index of the first bit, which is 1 in resultExclusiveOR unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR); num1 = num2 = 0; for (int j = 0; j < length; ++ j) { // divide the numbers in data into two groups, // the indexOf1 bit of numbers in the first group is 1, // while in the second group is 0 if(IsBit1(data[j], indexOf1)) num1 ^= data[j]; else num2 ^= data[j]; } } int main() { int a[8] = {2,3,6,8,3,2,7,7}; int x,y; FindNumsAppearOnce(a,8,x,y); cout<<x<<"\t"<<y<<endl; return 0; }
题目：一个整型数组里有三个数字出现了一次，其他的数字都出现了两次。请写程序找出这3个只出现一次的数字。
分析：思路类似于上题，关键是找出第一个来，然后借助上题结论求另外两个。
假设x y z为只出现一次的数，其他出现偶数次。lowbit为某个数从右往左扫描第一次出现1的位置，则x^y、 x^z、 y^z 这三个值的lowbit有一个规律，其中肯定两个是一样的，另外一个是不一样的。令flips为上述三个值的异或，即flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)。因此，可以利用此条件获得某个x(或者y，或者z)，循环判断的条件是a[i]^xors的lowbit==flips（其中xors为所有数的异或值）
解释：a[i]^xors即可划分为两组，一组是lowbit与flips不同，一组是lowbit与flips相同。这样就能找到某个x,y,z，找出后，将其与数组最后一个值交换，在利用上题思路，在前面n-1个数中找出剩余两个。
#include <iostream> using namespace std; int lowbit(int x) { return x & ~(x - 1); } void Find2(int seq[], int n, int& a, int& b) { int i, xors = 0; for(i = 0; i < n; i++) xors ^= seq[i]; int diff = lowbit(xors); a = 0,b = 0; for(i = 0; i < n; i++) { if(diff & seq[i]) //与运算，表示数组中与异或结果位为1的位数相同 a ^= seq[i]; else b ^= seq[i]; } } //三个数两两的异或后lowbit有两个相同，一个不同，可以分为两组 void Find3(int seq[], int n, int& a, int& b, int& c) { int i, xors = 0; for(i = 0; i < n; i++) xors ^= seq[i]; int flips = 0; for(i = 0; i < n; i++) //因为出现偶数次的seq[i]和xors的异或，异或结果不改变 flips ^= lowbit(xors ^ seq[i]); //表示的是：flips = lowbit(a^b) ^ lowbit(a^c) ^ lowbit(b^c) //三个数两两异或后lowbit有两个相同，一个不同，可以分为两组 //所以flips的值为：lowbit(a^b) 或 lowbit(a^c) 或 lowbit(b^c) //得到三个数中的一个 a = 0; for(i = 0; i < n; i++) { if(lowbit(seq[i] ^ xors) == flips) //找出三个数两两异或后的lowbit与另外两个lowbit不同的那个数 a ^= seq[i]; } //找出后，与数组中最后一个值交换，利用Find2，找出剩余的两个 for(i = 0; i < n; i++) { if(a == seq[i]) { int temp = seq[i]; seq[i] = seq[n - 1]; seq[n - 1] = temp; } } //利用Find2，找出剩余的两个 Find2(seq, n - 1, b, c); } //假设数组中只有2（010）、3（011）、5（101）三个数，2与3异或后为001，2与5异或后为111，3与5异或后为110， //则flips的值为lowbit(001)^lowbit(111)^lowbit(110)= 2 ，当异或结果xors与第一个数2异或的时候，得到的就是3与5异或的结果110，其lowbit值等于flips，所以最先找出来的是三个数中的第一个数：2 int main(void) { int seq[]={ 2,3,3,2,4,6,4,10,9,8,8 }; int a,b,c; Find3(seq, 11, a, b, c); cout<<a<<endl; cout<<b<<endl; cout<<c<<endl; return 0; }
本文转自阿凡卢博客园博客，原文链接：http://www.cnblogs.com/luxiaoxun/archive/2012/09/08/2676610.html，如需转载请自行联系原作者
