【位运算】消失的两个数字

admin管理员组

文章数量:1439825

【位运算】消失的两个数字

面试题 17.19. 消失的两个数字

面试题 17.19. 消失的两个数字

​ 给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

​ 以任意顺序返回这两个数字均可。

示例 1:

代码语言：javascript代码运行次数：0运行复制

输入: [1]
输出: [2,3]

示例 2:

代码语言：javascript代码运行次数：0运行复制

输入: [2,3]
输出: [1,4]

提示：

• nums.length <= 30000

---

解题思路

​ 这道题其实就是 268. 丢失的数字 和 137. 只出现一次的数字 II 的一个组和题，只要这两道题会了，然后稍微变化一下就变成了这道题！无非就是这道题出现一次的数字是两个，而我们得像 268. 丢失的数字 这道题一样去遍历所有的整数两次，换在 137. 只出现一次的数字 II 这道题上无非就是其它数字出现了两次！

​ 也就是说，这道题转化为了：一个数组中从 [1, n] 的数字只有两个数字出现了一次，而其它数字出现了两次！这个转化很关键！

1. 首先，我们用一个变量 n，去遍历【异或上】 nums 数组中的每一个元素，然后再去遍历【异或上】 [1, nums.size() + 2] 区间内所有的数字，最后显而易见，那些出现了两次的数字，在两次的遍历之后都被抵消了，所以最后得到的 n 就是两个只出现一次的元素的异或体，假设这两个出现一次的元素分别是 a 和 b，那么 n = a ^ b。
2. 接着，我们考虑一个性质：因为 a 和 b 一定是不同的，所以 n 的比特位中一定会存在某些位为 1（因为异或之后，相异的比特位得到的就是 1），而这些比特位对于 a 和 b 来说，不是 a = 1，b = 0，就是 a = 0，b = 1，那么我们只需要根据找到 n 中比特位为 1 的其中一个位置 pos（代码中我们是找最右侧的那个），然后再到 nums 数组中遍历一遍，根据每个数字的 pos 处比特位的值进行划分，这里规定 pos 处比特位为 1 的划分存在 a 的集合 seta 中，而为 0 的划分在存在 b 的集合 setb 中，最后得到的就是一个不含有 a 的异或集合，一个不含有 b 的异或集合！
3. 此时 问题就转化为了分别求 seta 和 setb 中在 [0, nums.size() + 2] 上消失的那个数字，那不就很简单了吗，我们只需要让 seta 和 setb （此时这两个集合存放的是 nums 中出现一次的数字）分别去遍历一次 [1, nums.size() + 2] 上所有数字，最后出现一次的那些数字因为遍历第二遍后都被抵消了，而那个消失的数字就会在最后的异或结果被得到，两个集合都是如此！

​ 解析有点绕，建议画图跟着分析，代码如下所示：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 1. 假设丢失的是a和b，那么先异或上全部元素，得到的结果就是a^b
        int n = 0;
        for(int i = 0; i < nums.size(); ++i)
            n ^= nums[i];
        for(int i = 1; i <= nums.size() + 2; ++i)
            n ^= i;
        
        // 2. 找到a和b比特位中为1的其中一个位置（a和b是不同的，所以一定存在这个比特位为1）
        int pos = 0;
        while(true)
        {
            if((n >> pos) & 1)
                break;
            pos++;
        }

        // 3. 根据这个相异的比特位就能划分成两个集合seta和setb
        int seta = 0, setb = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            if((nums[i] >> pos) & 1)
                seta ^= nums[i];
            else
                setb ^= nums[i];
        }

        // 4. 此时就是分别在seta和setb中找只存在一次的数，也就是a和b，那么只需要再遍历异或一遍所有整数即可
        for(int i = 1; i <= nums.size() + 2; ++i)
        {
            if((i >> pos) & 1)
                seta ^= i;
            else
                setb ^= i;
        }
        return { seta, setb };
    }
};

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-14，如有侵权请联系 cloudcommunity@tencent 删除前往查看集合数组int遍历变量

本文标签： 位运算消失的两个数字