LeetCode 448.找到所有数组中消失的数字 - JavaScript

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

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

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

题目分析

这一题和Leetcode 442.数组中重复的数据解决思路很相似。但没有完全明确的限制空间使用。

解法 1：哈希表

算法流程如下：

• 准备一个哈希表 map，结构是number-boolean
• 遍历原数组，将每个元素在 map 中的值设为 true
• 从 1 到 n，检查map[i]是否为 true。若是 true，说明出现在原数组中；否则是没出现过。

这个过程需要为哈希表开辟 O(N)空间，时间复杂度是 O（N）。代码如下：

// ac地址：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
// 原文地址：https://xxoo521.com/2020-02-14-find-all-numbers-disappeared-in-an-array/

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    const length = nums.length;
    if (!length) {
        return [];
    }

    const map = {};
    nums.forEach(num => (map[num] = true));

    const res = [];
    for (let i = 1; i <= length; ++i) {
        if (!map[i]) res.push(i);
    }

    return res;
};

解法 2: 原地哈希

和Leetcode 442.数组中重复的数据的解法相似：使用符号来标记元素是否出现过。下标为 i 的元素的符号，代表着值为 i + 1 的元素是否出现过，负号是出现过，正号是没出现过。

不需要开辟空间给哈希表，时间复杂度是 O（N）。代码实现如下：

// ac地址：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
// 原文地址：https://xxoo521.com/2020-02-14-find-all-numbers-disappeared-in-an-array/

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    const length = nums.length;
    if (!length) {
        return [];
    }

    nums.forEach(num => {
        // 将下标为 abs(num) - 1 的元素变成负数
        const absNum = Math.abs(num);
        if (nums[absNum - 1] > 0) {
            nums[absNum - 1] *= -1;
        }
    });

    const res = [];
    // 针对“数组下标”进行遍历
    for (let i = 1; i <= length; ++i) {
        // 如果下标 i-1 的元素是正数，说明整数 i 没出现过（要不然前面循环就变成负数了）
        if (nums[i - 1] > 0) {
            res.push(i);
        }
    }

    return res;
};

更多资料

• ??Blog：剑指 Offer/LeetCode 题解 + JS 代码
• ??Github ：https://github.com/dongyuanxin/blog
• ?? 公众号：心谭博客