初识算法 · 位运算(end)

_lazy

发布于 2024-11-19 10:33:27

5600

代码可运行

文章被收录于专栏：Initial programming

运行总次数：0

代码可运行

前言：

本文作为初识算法 · 位运算的最后一篇文章，使用一道hard题目来结束这个专题，题目的链接为：

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

还是和前文一样，通过三个部分介绍，题目解析，算法原理，算法编写来介绍。

那么话不多说，进入主题吧！

题目解析

题目的要求十分简单，是让我们在一段连续数字区间里面找到缺失两个数字，数字的区间是从1到N的。要求非常简单。

所以我们直接进入到算法原理部分。

算法原理

这道题目其实是丢失的数字和只出现一次的数字III的结合，链接为：

268. 丢失的数字 - 力扣（LeetCode）

260. 只出现一次的数字 III - 力扣（LeetCode）

结合两道题目的描述，我们就直到就是这两个结合起来嘛，所以使用异或运算律，将数集分为两组是肯定的，可是这里一共只有一段区间，我们去哪里找呢？简单，我们自己创一个区间不就行了吗？

因为这道题目可以分析为，在一堆数字里面，只有两个数字出现了一次，其他数字出现了两次。

所以使用异或，将其他数字全部干掉的同时，使用异或运算，将数分组，所以a和在某个比特位上同组的数字异或，b同理，最后的结果就是我们的答案。

这道题可以使用ret & -ret，也可以直接while找，都是可以的。

算法编写

class Solution 
{
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        //两堆数字异或
        int tmp = 0;
        for(auto e : nums) tmp ^= e;
        for(int i = 0;i <= nums.size() + 2; i++) tmp ^= i;
        //找出不同
        int diff = 0;
        while(1)
        {
            if(((tmp >> diff) & 1) == 1) break;
            else diff++;
        }
        //开始分组
        int a = 0, b = 0;
        for(int x : nums)
            if(((x >> diff) & 1) == 1) a ^= x;
            else b ^= x;
        for(int i = 0; i <= nums.size() + 2; i++)
            if(((i >> diff) & 1) == 1) a ^= i;
            else b ^= i;

        return { a, b };
    }
};

感谢阅读！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-19，如有侵权请联系 cloudcommunity@tencent.com 删除

原理