LeetCode 448.找到所有数组中消失的数字 - JavaScript
LeetCode 448.找到所有数组中消失的数字 - JavaScript
心谭博客
发布于 2020-04-21 10:44:44
发布于 2020-04-21 10:44:44
题目描述：给定一个范围在 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;
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-02-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录