算法与数据结构 · 实战

LC:268.丢失的数字

本文写于 2021 年,涉及的组件版本、配置与数据可能已过时,请按经验材料阅读并核对当前版本。原文链接与内容保持不变。

题目

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

进阶

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

相关题目

相关链接

分析

简单类型的题目。 先把题目读清楚: 区间[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;
}

最后

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

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

配套资料 · 免费领取
本文属于「ALGO」资料包范围:算法系列合订 + 刷题清单。LeetCode 与杭电 OJ 的题解索引。
在公众号「方家小白」回复关键词 ALGO 即可领取。全文无需关注即可阅读。
ALGO