LC 268. 丢失的数字

题目描述

这是 LeetCode 上的 268. 丢失的数字 ，难度为 简单。

给定一个包含 $[0, n]$ 中 $n$ 个数的数组 $nums$ ，找出 $[0, n]$ 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]

输出：2

解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]

输出：2

解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]

输出：8

解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：

输入：nums = [0]

输出：1

解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：

• $n = nums.length$
• $1 <= n <= 10^4$
• $0 <= nums[i] <= n$
• nums 中的所有数字都独一无二

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

---

排序

一个简单的做法是直接对 $nums$ 进行排序，找到符合 $nums[i] \neq i$ 的位置即是答案，如果不存在 $nums[i] \neq i$ 的位置，则 $n$ 为答案。

Java 代码：

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) return i;
        }
        return n;
    }
}

C++ 代码：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) return i;
        }
        return n;
    }
};

• 时间复杂度：$O(n\log{n})$
• 空间复杂度：$O(\log{n})$

---

数组哈希

利用 $nums$ 的数值范围为 $[0,n]$，且只有一个值缺失，我们可以直接开一个大小为 $n + 1$ 的数组充当哈希表，进行计数，没被统计到的数值即是答案。

Java 代码：

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        boolean[] hash = new boolean[n + 1];
        for (int x : nums) hash[x] = true;
        for (int i = 0; i < n; i++) {
            if (!hash[i]) return i;
        }
        return n;
    }
}

C++ 代码：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        vector<bool> hash(n + 1, false);
        for (int x : nums) hash[x] = true;        
        for (int i = 0; i < n; i++) {
            if (!hash[i]) return i;
        }
        return n;
    }
};

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

---

原地哈希

事实上，我们可以将 $nums$ 本身作为哈希表进行使用，将 $nums[i]$ 放到其应该出现的位置 $i$ 上（ $i < n$ ），然后对 $nums$ 进行检查，找到满足 $nums[i] \neq i$ 的位置即是答案，如果不存在 $nums[i] \neq i$ 的位置，则 $n$ 为答案。

Java 代码：

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] != i && nums[i] < n) swap(nums, nums[i], i--);
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) return i;
        }
        return n;
    }
    void swap(int[] nums, int i, int j) {
        int c = nums[i];
        nums[i] = nums[j];
        nums[j] = c;
    }
}

C++ 代码：

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

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

---

作差法

利用 $nums$ 的数值范围为 $[1, n]$，我们可以先计算出 $[1, n]$ 的总和 $sum$（利用等差数列求和公式），再计算 $nums$ 的总和 $cur$，两者之间的差值即是 $nums$ 中缺失的数字。

Java 代码：

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int cur = 0, sum = n * (n + 1) / 2;
        for (int x : nums) cur += x;
        return sum - cur;
    }
}

C++ 代码：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int cur = 0, sumv = n * (n + 1) / 2;
        for (int x : nums) cur += x;
        return sumv - cur;
    }
};

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

---

异或

找缺失数、找出现一次数都是异或的经典应用。

我们可以先求得 $[1, n]$ 的异或和 $ans$，然后用 $ans$ 对各个 $nums[i]$ 进行异或。

这样最终得到的异或和表达式中，只有缺失元素出现次数为 $1$ 次，其余元素均出现两次（$x ⊕x = 0$），即最终答案 $ans$ 为缺失元素。

Java 代码：

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length, ans = 0;
        for (int i = 0; i <= n; i++) ans ^= i;
        for (int x : nums) ans ^= x;
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int i = 0; i <= n; i++) ans ^= i;
        for (int x : nums) ans ^= x;
        return ans;
    }
};

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

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.268 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。