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

题目描述

本题目来自LeetCode上的『面试题 17.19. 消失的两个数字』

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

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

示例1：

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

提示

nums.length <= 30000

题解1 - 鸽巢原理

将原数组再加上两个 -1 元素，然后根据鸽巢原理进行排序，将每个元素放到对应下标处，剩下两个没有对应元素的下标则会被 -1 占据，找到这两个下标即可。

代码

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

复杂度分析

时间复杂度：$O(n)$
空间复杂度：$O(1)$

题解2 - 一元二次方程

设缺失的两个数为 $x,y$ ，数组大小为 $n$，易得以下两个式子：
$$
x+y=\sum_{a=1}^{N}a-\sum_{i=0}^{n}nums[i]
$$

$$
x\times y=\prod_{a=1}^{N}a-\prod_{i=0}^{n}nums[i]
$$

上述两个式子联立得一个一元二次方程，方程的根就是缺失的两个值。

注：使用模运算，防止出现溢出问题。使用模运算下的乘法逆来代替除法，防止出现浮点数的精度问题。$MOD=1e9+7$

代码

class Solution {
private:
    static constexpr int MOD = 1e9 + 7;
    typedef long long ll;
    int pow(ll x, int n) {
        ll res = 1;
        for (; n; n >>= 1) {
            if (n & 1) res = res * x % MOD;
            x = x * x % MOD;
        }
        return res;
    }
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size(), m = n + 2;
        int sum = m * (m + 1) / 2;
        ll prod = 1, inverse = 1;

        for (const auto& num : nums) sum -= num;
        for (int i = 1; i <= m; ++i) prod = prod * i % MOD;
        for (const auto& num : nums) inverse = inverse * num % MOD;

        inverse = pow(inverse, MOD - 2);
        prod = prod * inverse % MOD;

        int delta = sqrt(sum * sum - 4 * prod);
        return {(sum - delta) / 2, (sum + delta) / 2};
    }
};

复杂度分析

时间复杂度：$O(n)$
空间复杂度：$O(1)$

题解3 - 位运算

将 $[1,N]$ 加入到数组后面，那么除了缺失的两个数 $x,y$，其他的数字都会出现两次，通过异或操作，相同的数字异或值为 $0$，那么数组所有元素的异或和为 $a=x\oplus y$。

通过 $a&(-a)$ 可以得到 $a$ 的最低位的 $1$，则 $x,y$ 对应位一定只有一个 $1$，另一个为 $0$。由此将数组分为两类（该位是否为 $1$），且 $a$ 和 $b$ 在不同的类中。

在每一类中，除了 $a$ 或 $b$，其他的都出现了两次，再通过异或操作即可分别求出 $a$ 和 $b$。

代码

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int xorsum = 0;
        int n = nums.size() + 2;
        for (int num : nums) xorsum ^= num;
        for (int i = 1; i <= n; i++) xorsum ^= i;

        int mask = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
        int type1 = 0, type2 = 0;

        for (int num : nums) {
            if (num & mask) type1 ^= num;
            else type2 ^= num;
        }
        for (int i = 1; i <= n; i++) {
            if (i & mask) type1 ^= i;
            else type2 ^= i;
        }
        
        return {type1, type2};
    }
};