在做题中学习(36):消失的两个数字

发布时间:2023年12月21日

面试题 17.19. 消失的两个数字 - 力扣(LeetCode)

思路:丢失的数字 + 只出现一次的数字III

ps: 下面讲 丢失的数字 思路,另一个在前面的(32)。

丢失的数字:给定一个包含?[0, n]?中?n?个数的数组?nums?,找出?[0, n]?这个范围内没有出现在数组中的那个数。

异或特点:a ^ 0 = a;?

? ? ? ? ? ? ? ? ? a ^?a = 0;

? ? ? ? ? ? ? ? ? a ^ (b ^ c) = (a ^ b) ^ c;?

思路:用异或的几种规则可以想到,让一个数先异或数组中的数字一遍,再异或从0->n所有数字一遍,最后得到的数字就是丢失的数字。

下面的代码注释我也写的很详细了。

class Solution 
{
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        int ret=0;
        //异或数组内的
        for(auto e:nums)
        {
            ret ^= e;
        }
        //异或从1--N所有
        for(int i=1;i<=nums.size()+2;i++)
        {
            ret ^= i;
        }
        //走到这里ret已经是两个缺失的数字的异或了
        //接下来找最低位1
        int lowbit = ret&(-ret);
        int count = 0;
        while(lowbit!=1)
        {
            lowbit = lowbit>>1;
            count++;
        }
        //知道两个数在第count位就不一样了,以此分组
        int a = 0, b = 0;
        for(auto e:nums)
        {
            if(((e>>count)&1)==1)
            {
                a ^= e;
            }
            else
            {
                b ^= e;
            }
        }
        for(int i=1;i<=nums.size()+2;i++)
        {
            if(((i>>count)&1)==1)
            {
                a ^= i;
            }
            else
            {
                b ^= i;
            }
        }
        return {a,b};
    }
};










文章来源:https://blog.csdn.net/yiren_liusong/article/details/135135137
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。