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

题解

思路一

先排序,然后找出那个数即可。
时间复杂度O(nlogn)
空间复杂度O(logn)

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
const missingNumber = function (nums) {
    // 排序
    nums.sort((a, b) => a - b);
    // 假设丢失的数是0
    let n = 0;
    for (let num of nums) {
        // 如果丢失的数不在数组中,则中断循环;否则这个数自增
        if (n === num) {
            n++;
        } else {
            break;
        }
    }
    return n;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

思路二

算出[0,n]之间的和减去数组各元素之和就是缺失的那个元素
时间复杂度O(n)
空间复杂度O(1)

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
const missingNumber = function (nums) {
    const n = nums.length;
    const total = (n + 1) * n / 2;
    const sum = nums.reduce((a, b) => a + b, 0);
    return total - sum;
};
1
2
3
4
5
6
7
8
9
10

运行结果