来自剑指offer
分析:
如果整型数组中只有一个数字出现一次,我们只需将数组中每个元素依次做异或操作,最终就得到了只出现一次的数字。因为自己与自己异或后,结果为0.
现在,数组中有两个数字只出现一次,上述一次遍历后将所有元素异或得不到那两个数字。因此,我们试着将原数组分成两个子数组,使每个子数组中分别包含一个只出现一次的数字,而其他数字都是出现两次。所有,此时,数组如何去拆分呢?
例如,数组2,4,3,6,3,2,5,5,当我们依次对所有元素做一次异或操作后,得到的二进制位0010,我们可以按照数字倒数第二位是不是1分为两组数组。第一组为2,3,6,3,2;第二组为4,5,5。接下只要对每个子数组求异或,就能找到4和6了。
代码:
void FindNumsAppAppearOnce(int* data, int length, int* num1, int* num2) { if(data==NULL || length<2) return; int resultExclusiveOR = 0; for (int i = 0; i < length; i++) resultExclusiveOR ^= data[i]; unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR); *num1 = *num2 = 0; for (int j = 0; j < length; j++) { if ( IsBit1(data[j], indexOf1) ) *num1 ^= data[j]; else *num2 ^= data[j]; } } //判断resultExclusiveOR二进制中从右到左第一个1出现的位置 int FindFirstBitIs1(int resultExclusiveOR) { int indexBit = 0; while ( ((resultExclusiveOR&1)==0) && (indexBit < 8*sizeof(int)) ) { resultExclusiveOR = resultExclusiveOR>>1; indexBit++; } return indexBit; } //判断num的第index是否为1,是返回1,不是返回0; bool IsBit1(int num, unsigned int index) { num = num>>index; return (num&1); }