268-丢失的数字(Missing Number)

原文链接: https://leetcode-cn.com/problems/missing-number

英文原文

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Example 4:

Input: nums = [0]
Output: 1
Explanation: n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

Constraints:

n == nums.length
1 <= n <= 10⁴
0 <= nums[i] <= n
All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

中文题目

给定一个包含 [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⁴
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

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

通过代码

高赞题解

系统排序

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

代码；

[]
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;
    }
}

时间复杂度：假定 Arrays.sort 使用的是双轴快排实现。复杂度为 $O(n\log{n})$
空间复杂度：$O(\log{n})$

数组哈希

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

代码：

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

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

原地哈希

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

代码：

[]
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;
    }
}

时间复杂度：每个元素会被一次性移动到对应位置，因此每个元素的访问次数为常数次。复杂度为 $O(n)$
空间复杂度：$O(1)$

作差法

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

代码：

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

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

异或

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

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

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

代码：

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

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

最后

题太简单？不如来学习热乎的 $Trie$ 四部曲的最终章「可删除/可计数/持久化」Trie ，相关阅读：

或是加练如下「位运算」内容 🍭🍭🍭

题目	题解	难度	推荐指数
137. 只出现一次的数字 II	LeetCode 题解链接	中等	🤩🤩🤩
190. 颠倒二进制位	LeetCode 题解链接	简单	🤩🤩🤩
191. 位1的个数	LeetCode 题解链接	简单	🤩🤩🤩
231. 2 的幂	LeetCode 题解链接	简单	🤩🤩🤩
260. 只出现一次的数字 III	LeetCode 题解链接	中等	🤩🤩🤩🤩
268. 丢失的数字	LeetCode 题解链接	简单	🤩🤩🤩🤩
338. 比特位计数	LeetCode 题解链接	简单	🤩🤩🤩
342. 4的幂	LeetCode 题解链接	简单	🤩🤩🤩
371. 两整数之和	LeetCode 题解链接	中等	🤩🤩🤩🤩
405. 数字转换为十六进制数	LeetCode 题解链接	简单	🤩🤩🤩🤩
461. 汉明距离	LeetCode 题解链接	简单	🤩🤩🤩🤩
476. 数字的补数	LeetCode 题解链接	简单	🤩🤩🤩🤩
477. 汉明距离总和	LeetCode 题解链接	简单	🤩🤩🤩🤩
526. 优美的排列	LeetCode 题解链接	中等	🤩🤩🤩
1178. 猜字谜	LeetCode 题解链接	困难	🤩🤩🤩🤩
1711. 大餐计数	LeetCode 题解链接	中等	🤩🤩🤩
剑指 Offer 15. 二进制中1的个数	LeetCode 题解链接	简单	🤩🤩🤩

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或加入「组队打卡」小群，提供写「证明」&「思路」的高质量题解。

所有题解已经加入刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
195247	299992	65.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
缺失的第一个正数	困难
只出现一次的数字	简单
寻找重复数	中等
情侣牵手	困难

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途