268.丢失的数字:「排序」&「计数」&「原地哈希」&「

「这是我参与11月更文挑战的第 6 天，活动详情查看：2021最后一次更文挑战」。

题目描述

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

Tag : 「模拟」、「哈希表」、「位运算」、「数学」

给定一个包含

[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$

  1<=n<=104

• 
  $0 <= nums[i] <= n$

  0<=nums[i]<=n

• nums 中的所有数字都 独一无二

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

系统排序

一个简单的做法是直接对

nums 进行排序，找到符合

nums[i]=i 的位置即是答案，如果不存在

nums[i]=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(nlogn)

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

  O(logn)

数组哈希

利用

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)

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

  O(n)

原地哈希

事实上，我们可以将

nums 本身作为哈希表进行使用，将

nums[i] 放到其应该出现的位置

i 上（

i<n ），然后对

nums 进行检查，找到满足

nums[i]=i 的位置即是答案，如果不存在

nums[i]=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(n)

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

  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(n)

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

  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(n)

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

  O(1)

最后

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

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

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

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