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

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

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

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

示例:

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

输出:
[5,6]

# 解(1):Map

    var findDisappearedNumbers = function (nums) {
    let map = new Map()
    let arr = []
    for (let i = 1; i <= nums.length; i++) {
        map.set(i, 1)
    }
    for (let i = 0; i < nums.length; i++) {
        if (map.get(nums[i])) {
            map.delete(nums[i])
        }
    }
    for (let key of map.keys()) {
        arr.push(key)
    }
    return arr
};

# 解(2):Set

var findDisappearedNumbers = function (nums) {
    let arr = []
    nums1 = [...new Set(nums)].sort((a, b) => a - b)
    for (let i = 0; i < nums.length; i++) {
        if (nums1[i] !== (i + 1)) {
            // 如果去重后的 num1 不存在这个值,则补充这个值
            nums1.splice(i, 0, (i + 1))
            arr.push(nums1[i])
        }
    }
    return arr
};
Last Updated: 4/3/2020, 6:21:54 PM