面试题56：数组中数字出现的次数

题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。要求时间复杂度O(n),空间复杂度O(1).
两不同数字异或为1 ，按位是否为1分成两组，则各只含一个不同数字。

class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int len = data.size();
if(data.empty() || len < 2)
return;
int resXOR = 0;
for(int i = 0; i < len; ++i)
resXOR ^= data[i];//找出两个不同数字的异或结果
int indexOf1 = findFirstBitIs1(resXOR);
*num1 = *num2 = 0;
for(int j = 0; j < len; ++j)
{
if(isBit1(data[j], indexOf1))
*num1 ^= data[j];
else
*num2 ^= data[j];
}
}
int findFirstBitIs1(int num)//找到右边起的第一个值为1的位
{
int indexBit = 0;
while((num & 1) == 0 && (indexBit < 8 * sizeof(int)))
{
num = num >> 1;
++ indexBit;
}
return indexBit;
}
bool isBit1(int num, int index)//判断num右起第index位是否为1
{
num = num >> index;
return (num & 1);
}
};

最后

以上就是哭泣期待为你收集整理的面试题56：数组中数字出现的次数的全部内容，希望文章能够帮你解决面试题56：数组中数字出现的次数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。