数组中只出现一次的两个数字

题目 数组中只出现一次的两个数字

image-2799e9d2

思路分析

在学异或的时候知道了怎么去找出只出现一次的一个数

原理就是 两个相同的数做异或等于没做 那把所有的数异或起来 结果就是这个出现一次的数了

但是这里有不一样的地方就是 出现一次的数有两个

也就是说 当我们把所有的数异或起来后 得到的那个值不是唯一的x了

而是x^y

那该怎么把x和y分别找出来呢

其实也很简单

他们之所以异或不为0 就说明x和y肯定存在一位不相同

那这不相同的一位就体现在 x^y的二进制表示中的1处

那么 就可以根据这个1 把所有的数分为两半

该位为1的一半和该位为0的一半

x和y一定各在一边

那这样就变成了一开始的问题 找一个出现一次的数 把所有该位为1的数异或起来

找到x后 y直接通过x^xy就可以得到了

代码实现

class Solution {

public:

    vector<int> findNumsAppearOnce(vector<int>& nums) {

        int xy=0;

        for(auto num:nums)

            xy^=num; //xy=x^y

        //找到xy中1的位置

        int k=0;

        while((xy>>k&1)==0)

            k++;

        //在对所有该位为1的数做一次异或（对所有该位为0的数做也行）

        int x=0;

        for(auto num:nums)

        {

            if((num>>k&1)==1)

            //if((num>>k&1)==0)

                x^=num;

        }

        //那么就有x^y x了 y直接把x^y再^一次x就可以得到

        int y=xy^x;

        return {x,y};

    }

};

同类题型

视频讲解

⬅️ 按要求计算 🏠 00-刷题理模型 ➡️ 数组中唯一只出现一次的数字