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

heray0 2020-02-16

题目描述:给定一个范围在 ? 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;
};

更多资料

相关推荐