LC:268. 丢失的数字 - LeetCode 系列 | 方家小白 = 和你一起遇见更好的自己

# 题目

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

# 示例

# 示例 1

1
2
3

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

# 示例 2

1
2
3

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

# 示例 3

1
2
3

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

# 示例 4

1
2
3

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

# 提示

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

# 进阶

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

# 相关题目

力扣（LeetCode）268.丢失的数字

https://leetcode-cn.com/

力扣（LeetCode）136. 只出现一次的数字

https://leetcode-cn.com/

力扣（LeetCode）287. 寻找重复数

https://leetcode-cn.com/

力扣（LeetCode）41. 缺失的第一个正数

https://leetcode-cn.com/

力扣（LeetCode）765. 情侣牵手

https://leetcode-cn.com/

# 分析

简单类型的题目。
先把题目读清楚：
区间 [0,n] 一共有 n+1 个数，而题目中说的是 [0,n] 是 n 个数的数组，所以只会少 1 个数字。

# 解法

# 解法一：排序

将数组 nums 进行排序，找到 nums[i]!=i 的位置，就是缺少的那个数。

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

# 解法二：额外数组

由于 [0,n] 是数字连续的。所以我们使用一个额外的 n+1 长度的数组 pos 。将 nums[i] 作为 pos 的索引赋值为 1 ，从 1 开始遍历 pos 数组， pos[i]==0 即为少的那个数字。

public int missingNumber(int[] nums) {
    int pos[] = new int[nums.length + 1];

    for (int i = 0; i < nums.length; i++) {
        pos[nums[i]] = 1;
    }

    for (int i = 1; i < pos.length; i++) {
        if (1 != pos[i]) {
            return i;
        }
    }
    return 0;
}

# 解法三：数学计算

区间 [0,n] 是连续的数组，那么利用等差数列的性质可以算出来 n 个数的总和，减去 nums 数组中的元素，则就是少的那个数。

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

# 解法四：亦或

亦或计算使然。 a^a=0 , 0^a=a .

所以将 0...n 和 nums[0...n] 进行亦或计算，则计算出来的值就是缺少的那个数。

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

# 最后

期望与你一起遇见更好的自己

# 题目

# 示例

# 示例 1

# 示例 2

# 示例 3

# 示例 4

# 提示

# 进阶

# 相关题目

# 分析

# 解法

# 解法一：排序

# 解法二：额外数组

# 解法三：数学计算

# 解法四：亦或

# 最后

LC:42.接雨水

不要再在用JDK11写JDK8的代码了!