2013-09-08 10:50:46
一个整型数组中，除了两个数字之外，其他数字都出现了2次，找出这两个只出现一次的数字，要求时间复杂度是O(N)，空间复杂度是O(1)。
小结：
- 任何数与0异或，结果仍为本身；
- 两个相同的数字异或，结果为0；
- 利用异或的以上两个特点，进行求解。
代码（测试暂未发现问题，欢迎交流指正！）：
#include <iostream>
#include <cassert>
using namespace std; typedef int DataType; //返回一个数字的二进制表示中最低位的1的位置
size_t GetNumberOfOnce(DataType number)
{
assert(number != ); size_t mask = ;
size_t cnt = ; while ( !(number & mask) )
{
++cnt;
number = number>>;
} return (cnt);
} //找出一个数组中仅出现一次的数字，通过pNumber1、pNumber2返回
void GetNumberOfOnce(DataType *array,size_t len,DataType *pNumber1,DataType *pNumber2)
{
assert(array != NULL);
assert(len >= ); *pNumber1 = ;
*pNumber2 = ;
size_t index = ;
size_t resXOR = array[]; for (index = ;index < len;++index)
{
resXOR ^= array[index];
} size_t positionOf1 = GetNumberOfOnce(resXOR);
size_t mask = << positionOf1; for (index = ;index < len;++index)
{
if (array[index] & mask) //任何数与0异或，结果仍为本身
{
*pNumber1 ^= array[index];
}
else
{
*pNumber2 ^= array[index];
}
}
} //测试GetNumberOfOnce函数
void TestGetNumberOfOnce()
{
DataType array[] = {,,,, ,,,, ,};
//DataType array[10] = {1, 6};
size_t len = ;
DataType number1 = ;
DataType number2 = ; GetNumberOfOnce(array,len,&number1,&number2);
cout<<"the numbers appear once are : "<<number1<<"\t"<<number2<<endl;
} int main()
{
TestGetNumberOfOnce();
return ;
}
测试结果：
the numbers appear once are :
请按任意键继续. . .