求数组中只出现一次的数字的算法

求数组中只出现一次的数字的算法2015-09-20题目: 一个整型数组里除了两个数字以外, 其他的数字都出现了两次. 请写程序找出这两个只出现一次的数字.

如果从头到尾依次异或数组中的每一个数字, 那么最终的结果刚好是那个只出现一次的数字.

根据结果数组二进制某一位为1, 以此分组, 为1的一组, 为0的一组, 再重新进行异或. 最后得出两个结果.

时间复杂度O（n）.

代码:

/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h>#include <stdlib.h>#include <string.h>size_t FindFirstBitIs1（int num） {size_t indexBit = 0;while （（num&1）==0 && indexBit<（8*sizeof（int））） {num >>= 1;++indexBit;}return indexBit;}bool IsBit1（int num, size_t indexBit） {num >>= indexBit;return （num&1）;}void FindNumsApprearOnce（int data[], int length, int* num1, int* num2） {if （data == NULL || length <= 0）return;int resultExclusizeOR = 0;for （int i=0; i<length; ++i）resultExclusizeOR ^= data[i];size_t indexOf1 = FindFirstBitIs1（resultExclusizeOR）;*num1 = *num2 = 0;for （int j=0; j<length; ++j） {if （IsBit1（data[j], indexOf1））*num1 ^= data[j];else*num2 ^= data[j];}}int main（void）{int data[] = {2, 4, 3, 6, 3, 2, 5, 5};int num1, num2;FindNumsApprearOnce（data, 8, &num1, &num2）;printf（"num1 = %d num2 = %d
", num1, num2）;}

输出:

num1 = 6 num2 = 4