求star

题目#

给定一个包含 [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 = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

解题:key:#

①求和取差值#

TIP

​ 既然已经确定了nums应该是0n,那么直接求出0n的和，然后减去给定的nums的和即可

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function (nums) {
    const sum = nums.length * (nums.length + 1) / 2
    let count = 0
    for (let i = 0; i < nums.length; i++) {
        count += nums[i]
    }
    return sum - count
};

②利用indexOf方法#

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

③利用Set类#

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

④位运算#

TIP

本题跟”只出现一次的数字”有点像

​ 利用异或运算的一些性质:

• 0 ^ n = n

• n ^ n = 0

• 维护一个变量res，每次循环都让他与nums中的数字和0-n做异或运算,最后剩下来的(也就是res的值)就是缺少的数字

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

⑤先排序，后遍历#

var missingNumber = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i) {
            return i;
        }
    }
    return n;
};