448 找到所有数组中消失的数字

题目

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

题解

1. 因题目中有要求不使用额外空间，所以下面的方法使用了修改原数组的方式。通过遍历，把数字对应的值变为负数；再次遍历，如果值为正数的 index，就是缺失的数字。

TIP

执行用时：128 ms, 在所有 JavaScript 提交中击败了 77.13% 的用户

内存消耗：45.6 MB, 在所有 JavaScript 提交中击败了 79.93% 的用户

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    let result = []

    for(let i =0;i<nums.length;i++) {
        let current = Math.abs(nums[i]) // 当前值
        // 因为下标使用 0 开始，所以需要设置 *值 - 1* 的数为负数
        //  >0 是为了当出现重复的数的之后，如果再次 * -1 的话，就不对了，所以进行过滤
        if(nums[current - 1] > 0 ) {
            nums[current - 1] *= -1
        }
    }

    for(let i=0;i<nums.length;i++) {
        // 如果为正数，则 index + 1 后为缺失的数字
        if(nums[i] > 0) {
            result.push(i+1)
        }
    }

    return result
};

2. 另外一种解法是空间复杂度为 O(n) 的，通过使用一个数组来储存遇到过的值，当数组里的值为 undefined 的情况下，说明该值为缺失的数。

TIP

执行用时：164 ms, 在所有 JavaScript 提交中击败了 42.31% 的用户

内存消耗：49.1 MB, 在所有 JavaScript 提交中击败了 22.68% 的用户

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    let list = [] // 用来储存遇到的值
    let result = []
    nums.forEach((item, index) => {
        list[item] = item
    })

    // 注意这里从 第二个值开始遍历，因为给定的值从 1 开始，那么数组里第 0 个元素肯定为空
    for(let i=1;i<=nums.length;i++) {
        if(list[i] == undefined) {
            result.push(i)
        }
    }
    return result
};