LeetCode算法题-268.缺失数字-javascript（二十六）

解法一（排序比对）

• 排序
• 一一比对

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

解法二（哈希-key:value）

• 利用哈希查询的O(1)的时间复杂度，优化查询时间
• 不需要排序

var missingNumber = function(nums) {
    var obj = {}
    for(let i = 0; i < nums.length; i++){
        obj[nums[i]] = 1
    }
    for(let i = 0; i < nums.length + 1; i++){
        if(!obj[i]){
            return i
        }
    }
    return -1
};

解法三（位运算）

位运算里的异或运算有一个特点，两次异或同一个数最后结果不变

如果是1-9的数字与下标进行以后运算，得到的值一定是那个未匹配上的

var missingNumber = function(nums) {
    let len = nums.length;
    for (let i = 0; i < nums.length; i++) {
        len ^= i ^ nums[i];
    }
    return len;
}

解法四（数学思路）

• 1-9的数组，总和何以得出(线性求和大家应该会吧。。。)
• 参数数组的总和可以求出，做差即可

var missingNumber = function(nums) {
    var len = nums.length
    var sum = len*(len+1)/2
    var res = 0
    for(let i = 0; i < len; i++){
       res += nums[i]
    }
    return sum-res
}