【每日算法Day 71】面试官想考我这道位运算题，结果我给出了三种解法

godweiyang

发布于 2020-03-24 11:11:56

5680

发布于 2020-03-24 11:11:56

文章被收录于专栏：算法码上来算法码上来算法码上来

题目链接

LeetCode 面试题 17.19. 消失的两个数字[1]

题目描述

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

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

示例1

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

示例2

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

提示：

题解

位运算

首先将数组里的数再加上到中所有的数构成一个更大的集合，那么问题就变成了一个数组里有两个数只出现了一次，其余数都出现了两次，求这两个数是多少？

是不是很熟悉？这其实就是 LeetCode 另一道位运算题目：

LeetCode 面试题56 - I. 数组中数字出现的次数[2]

首先还是常规套路，把所有的数异或起来，得到的值一定就是出现一次的两个数的异或值。

那么再回顾一道最基本的位运算题：

LeetCode 136. 只出现一次的数字[3]

也就是一个数组里有一个数只出现了一次，其余数都出现了两次，求这个数是多少？这就很简单了，只需要全部异或起来就是这个数的值了。

那么回到本题，有没有办法将这个数拆分成两个集合，每个集合都满足上面这种最简单的条件（只有一个数出现了一次）呢？

刚刚得到了两个只出现一次数字的异或值，那么中的就表示了这两个数那一位是不同的。那就很简单了啊，我们把所有个数那一位是的归为一个集合，那一位是的归为一个集合，那么这两个只出现一次的数一定会分属两个不同的集合。而其他出现了两次的数，每个数字都会在同一个集合里。

最后对两个集合分别求异或值，就得到了两个出现一次数的值了。

这里有个关键点，就是按照某一位为来划分两个集合，其实取任意一位是的位都是可以的。但是最简单的方法就是取最低位，因为这样可以采用位运算直接得到。

位运算系列还有一个进阶版：

LeetCode 137. 只出现一次的数字 II[4]

这题就与本题无关了，我们留着下次继续讲。

数学法

首先假设缺失的两个数字为。

令为数组中的元素和，为数组中的元素平方和。

再用到的元素和减去就得到了的值，记为。用到的元素平方和减去就得到了的值，记为。

最后只要解出下面这个二元二次方程组就行了：

用求根公式可以解出两个解是：

其中：

下标哈希

一个很直觉的方法就是，我新开辟一个大小为的数组，然后把数组中的元素都放在新数组中下标对应的位置，最后看哪两个位置没有数就行了。但是现在要用原地算法，不允许新开辟空间，那我们就只能直接放在原数组里面了。

首先我们还是得把原数组扩展到大小为，也就是在末尾增加个空间，数字就放。

然后遍历数组，对于来说，它的位置上最后放的应该是数字才对，而应该被放在下标为的位置。所以我们把移动到下标为的位置上去，但是位置上的数字怎么办呢？不能直接覆盖，不然就再也无法访问了，所以我们把它移动到下标的位置就行了。也就是说交换下标和位置上的两个数。

那么问题接着来了，位置上面的数对了，但是位置上面的数还是错的啊。那么只要继续重复交换操作，直到位置位置上面的数是，或者是就行了。

最后所有数都摆回正确位置了，再扫描一遍数组，如果，就说明这个数不在数组里。

这个方法理论上适合缺任意个数，只需要一开始在数组后面补上个就行了。

代码

位运算（c++）

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size();
        int x = 0;
        for (auto i : nums) x ^= i;
        for (int i = 1; i <= n+2; ++i) x ^= i;
        int lb = x & -x;
        int y = 0;
        for (auto i : nums) {
            if (i&lb) y ^= i;
        }
        for (int i = 1; i <= n+2; ++i) {
            if (i&lb) y ^= i;
        }
        return {y, y^x};
    }
};

数学法（c++）

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        long n = nums.size()+2;
        long S1 = accumulate(nums.begin(), nums.end(), 0);
        long S2 = 0;
        for (auto x : nums) S2 += x*x;
        long a = n*(n+1)/2-S1;
        long b = n*(n+1)*(2*n+1)/6-S2;
        long x = (a+sqrt(2*b-a*a))/2;
        long y = (a-sqrt(2*b-a*a))/2;
        return {x, y};
    }
};

下标哈希（c++）

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        for (int i = 0; i < 3; ++i) {
            nums.push_back(-1);
        }
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] != -1 && i != nums[i]) {
                swap(nums[i], nums[nums[i]]);
            }
        }
        vector<int> res;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == -1) res.push_back(i);
            if (res.size() == 2) break;
        }
        return res;
    }
};