LeetCode 面试题 17.04：消失的数字

注意事项：

• 第二个循环必须遍历 0 ~ n（即 i <= nums.size()）。
• 异或不会产生溢出问题，适合大范围整数。
• 时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

思路一：数组哈希

// 数组哈希
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // 0-n 共 n+1 个数，缺了一个，还剩 n 个
        // 开一个大小为 n+1 的数组，初始化值均为 0
        // 遍历这 n 个数，将其对应下标的位置标记为 1
        // 再遍历这个数组，值为 0 的位置的下标，就是缺失的数
        vector<int> v(nums.size() + 1, 0);
        for (auto e : nums) {
            v[e] = 1;
        }
        int i = 0;
        for (; i < v.size(); ++i) {
            if (v[i] == 0) break;
        }
        return i;
    }
};

思路二：数学求和

// 求和
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // 0-n 这些数 正确的和 为 total
        int total = nums.size() * (nums.size() + 1) / 2;
        int sum = 0;
        // 缺了一个数后的和 为 sum
        for (auto e : nums) sum += e;
        return total - sum; // 相差的值 即为 缺失的数字
    }
};

思路三：位运算

// 位运算
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // 数组中有 0-n 缺了一个，共 n 个数，再在后面添加 0 - n 这完全不缺 的 n + 1 个数
        // 则共有 2n+1 个数 2n+1 个数中，消失的数只出现了一次
        // 其他数，每个数都出现了两次
        // 一个数 和 0 异或 等于它本身 一个数 和 它本身异或 等于 0
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) res ^= nums[i];
        for (int i = 0; i <= nums.size(); ++i) res ^= i;
        return res;
    }
};

算法代码优化

• 可以选择使用 STL 自带的哈希容器优化，但非必须
• 其他方法无需优化

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> set;
        // 将这 n 个数 插入到 哈希 set
        for (auto e : nums) {
            set.insert(e);
        }
        int missing = -1;
        // 再遍历数字 0-n 那个数字没有出现，就是缺失的数字
        for (int i = 0; i <= nums.size(); i++) {
            if (set.count(i) == 0) {
                missing = i;
                break;
            }
        }
        return missing;
    }
};