LeetCode笔记：丢失的数字

问题

给定一个包含 [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 中的所有数字都 独一无二

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

解法一

思路：

1. 先把数组中的数字排序
2. 再遍历数组检查下标和数组的值是否能对应上，对应不上的就是缺省的值
3. 最后再另外考虑只有0的情况，和缺省的是最后一个数字的情况

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    const find = nums.sort((a,b) => a-b).findIndex((n,i) => {
        return n !== i 
    })
    return find !== -1 ? find : nums.length
};

解法二

思路：

遍历0 - n的数字，检查是不是存在于nums数组中，不在nums数组中的数字即是缺省的数字

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    for(let i = 0; i < nums.length + 1; i++){
        if(!nums.includes(i)){
            return i
        }
    }
};

解法三

思路：

根据上述解法二的思路，直接使用数组的includes方法性能不太好，我们切换成Set集合，使用Set的has查找元素，提升查询效率

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    const set = new Set(nums)
    for(let i = 0; i < nums.length + 1; i++){
        if(!set.has(i)){
            return i
        }
    }
};

参考

• 268. 丢失的数字