首页 > > 程序设计 > C/C++ >

面试题---找出数组中两个只出现一次的数

2018-06-17 23:00:19来源：未知阅读 ()

题目描述：给一个数组，里面有两个数只出现一次，其它的数都出现两次，请找出这两个数；

样例：输入 2 4 2 7 4 9

输出 7 9

思路：假定要找出的这两个数为x、y 把所有的数异或，结果是x与y异或的值，那么肯定不为0，那么这个值的二进制至少有一位为1，也就是说x和y的二进制在这一位上必定一个为0，一个为1，那么可以根据这一位把这个数组分成两个数组，x和y在不同的数组里，接下来对每个数组直接异或出的值就是结果了；

代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
int num1,num2;

int singleNumber(int nums[],int length)
{
    num1=num2=0;
    if(length<2) return -1;
    int re=0;
    for(int i=0;i<length;i++)
      re^=nums[i];

    int ind=0;
    while((re&1)==0&&(ind<8*sizeof(int)))
    {
        re=re>>1;
        ++ind;
    }
    for(int j=0;j<length;++j)
    {
        int t=(nums[j]>>ind)&1;
        if(t) num1^=nums[j];
        else num2^=nums[j];
    }
}
int main()
{
    int nums[100]={2,4,2,7,4,9};
    singleNumber(nums,6);
    cout<<num1<<" "<<num2<<endl;
    return 0;
}