从数组中找出只出现一次的两个数，数组中其他数都出现两次

75 阅读 0 评论 50 点赞

我是靠谱客的博主眼睛大冰淇淋，最近开发中收集的这篇文章主要介绍从数组中找出只出现一次的两个数，数组中其他数都出现两次，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：在数组中有两个数只出现一次，其他数均出现两次。问怎样快速找出这两个数。

方法一：

直接遍历整个数组，建成类似hash的数组。用原始数组中元素值当hash数组下标，出现次数当hash数组元素值。最后再遍历一次hash，找出值为1元素的下标。或者不用hash数组，用map的键值对。思想一样的。

时间复杂度：O(n)

空间复杂度：O(n)

还有没有更优的算法呢？联想到我们用位操作找出数组中只出现一次的元素的思想，这里同样可以用位操作找出只出现一次的两个元素。

方法二：(重要)

把两个只出现一次的数记为a、b

1、将数组中所有元素进行异或操作，因为相同的数异或为0，这样得到的结果就是a异或b的值。

2、因为a和b肯定不相等，所以第一步得到的结果肯定不为0.也就是说此结果写成二进制至少有一位是1，找到这个为1的下标。用这一位我们可以把数组中的数分成两部分，一部分是这一位为1的数，一部分是这一位为0的数。a和b肯定不在同一个部分。数组中原来相同的数肯定在同一个部分。

3、将这两部分数分别进行异或运算。最后每部分异或的结果就是a和b。

时间复杂度：O(n)

空间复杂度：O(1)

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

vector<int> FindTwoOnce(vector<int> num){
    if(num.size()<=2)               //对符合要求的num数组，只有两个元素则直接返回
        return num;
    int res=0;                      //存储数组所有元素异或的结果
    for(int i=0;i<num.size();i++){
        res ^= num[i];
    }
    int index=0;                    //存储异或结果二进制表示中，从右往左第一个为1的下标
    for(int i=0;i<32;i++){
        int temp=res;
        if((temp>>i) & 1 == 1){     //第i位为1
            index=i;
            break;
        }
    }
    vector<int> result;             //存储问题结果的数组
    result.push_back(0);
    result.push_back(0);
    for(int i=0;i<num.size();i++){
        if((num[i]>>index) & 1 == 1)//第i位是1的一类
            result[0] ^= num[i];
        else                        //第i位是0的一类
            result[1] ^= num[i];
    }
    return result;
}

int main(){
    vector<int> num;
    num.push_back(2);
    num.push_back(2);
    num.push_back(3);
    num.push_back(4);
    num.push_back(5);
    num.push_back(5);
    vector<int> result=FindTwoOnce(num);
    cout<<result[0]<<' '<<result[1]<<endl;
    return 0;
}

继续思考：

位操作可以在数组中找出只出现一次的一个元素；只出现一次的两个元素。那么数组中有三个元素只出现一次，其他元素都出现两次，用位操作运算可以找出这三个数吗？

答案是可以用位运算找出这三个数。

将数组中所有的数进行异或运算，最后得到的是abc异或的结果。对此结果找到为1的那一位，用此位对数组分成两类。必有一类它的数字个数是奇数。这一类可能同时包含abc，也可能只包含abc其中一个。如果只包含abc其中一个，那么问题就变成了数组中有一个数只出现一次、数组中有两个数只出现一次，问题解决了。如果同时包含abc，那么继续上面的操作直到得到一部分只包含abc其中一个为止，问题也解决了。