面试中遇到的一道算法题

Question

有一堆数，其中有两个数出现了一次，其他的数都出现了两次。怎样将这两个只出现一次的数找出来？
排除打表，统计外有什么更为高效的方法。

Answer 1

参考我的文章 http://www.cnblogs.com/zichi/... 第三小节

PS：平时没事可以做做 leetcode，我的题解 repo https://github.com/hanzichi/l...

Answer 2

1先把所有数字 做 异或操作 得到数字 S
2 从高到低位检查 S 的 bit 找到第一个 1
3 检查所有数字 根据 这个bit位是1 还是 0 把 原来的数组划分为 两个
4 对每个数组 ，把数组内的数字做 异或操作。分别得到数字 A ,B
5 数字 A ,B 即为所求

时间复杂度 O(n)
空间复杂度 O(1)

Answer 3

剑指offer上的一题，用三次异或操作。

Answer 4

----update----
想了很久，发现貌似第一次^可以把两个数的高位的不同找出来。
但是低位可能相同，然后等于是相同的数就丢失信息了。

比如 6 10 ^结果是12 -> 0110 1010 ^后，这样12就是1100
高位就是11
而低位可能是00 01 10 11，但是由于^，两个相同的就等于丢失了。

那么可以取最高位的1，,构成1000 就是8 然后对小于这个数的做一次^就可以找出第一个数了。
那么另外一个数也可以找出来。

这样应该是对的吧。写一个验证一下。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{
    vector<int>arr{1,1,6,2,4,2,4,8,9,9,8,10};
    int result=0;
    for(auto i:arr)
        result^=i;
    cout<<result<<endl;
    auto i=result;
    i |= (i >> 1);
    i |= (i >> 2);
    i |= (i >> 4);
    i |= (i >> 8);
    i |= (i >> 16);
    int pos=i ^ (i >> 1);
    cout<<pos<<endl;
    int a=0,b=0;
    for(auto i:arr)
    {
        if(i>pos)
            a^=i;
        else
            b^=i;
    }
    cout<<a<<" "<<b<<endl;
    getchar();
}

----update-----

错误删了……

抱歉，我想得太简单了。

Answer 5

应该可以用桶排序