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

🟢   🔖  数组 哈希表  🔗 力扣 LeetCode

题目

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]

Output: [5,6]

Example 2:

Input: nums = [1,1]

Output: [2]

Constraints:

• n == nums.length
• 1 <= n <= 10^5
• 1 <= nums[i] <= n

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

题目大意

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入： nums = [4,3,2,7,8,2,3,1]

输出：[5,6]

示例 2：

输入： nums = [1,1]

输出：[2]

提示：

• n == nums.length
• 1 <= n <= 10^5
• 1 <= nums[i] <= n

进阶： 你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

解题思路

为了在 O(n) 时间复杂度和 O(1) 空间复杂度的条件下解决这个问题，我们可以利用数组的原地修改来标记已经出现过的数字。具体来说，利用数组元素值的符号来标记已经出现的数字，从而避免使用额外空间。

1. 数组 nums 中的每个元素都在 [1, n] 区间内，可以通过将数组元素 nums[i] 的值作为数组的索引来表示该数字是否出现过。
2. 遍历数组 nums，对于每个元素 num，将对应的索引 num - 1 位置的值变为负数，这样可以标记该位置对应的数字已经出现。
3. 最后，遍历数组 nums，查找所有值为正数的元素，它们的索引对应的数字就是没有出现过的数字。

复杂度分析

• 时间复杂度：O(n)。遍历数组两次，每次遍历的时间复杂度是 O(n)。
• 空间复杂度：O(1)。只使用了常数空间来存储结果数组 result，不需要额外的空间。

代码

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

	// 标记出现过的数字
	for (let i = 0; i < nums.length; i++) {
		let num = Math.abs(nums[i]);
		if (nums[num - 1] > 0) {
			nums[num - 1] = -nums[num - 1]; // 将对应位置标记为负
		}
	}

	// 查找未出现的数字
	for (let i = 0; i < nums.length; i++) {
		if (nums[i] > 0) {
			result.push(i + 1); // 将未出现的数字加入结果
		}
	}

	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
41	缺失的第一个正数	[✓]	数组 哈希表	🔴	🀄️ 🔗
442	数组中重复的数据	[✓]	数组 哈希表	🟠	🀄️ 🔗
1980	找出不同的二进制字符串		数组 哈希表 字符串 1+	🟠	🀄️ 🔗
2195	向数组中追加 K 个整数		贪心 数组 数学 1+	🟠	🀄️ 🔗
2295	替换数组中的元素		数组 哈希表 模拟	🟠	🀄️ 🔗
2554	从一个范围内选择最多整数 I	[✓]	贪心 数组 哈希表 2+	🟠	🀄️ 🔗
2557	从一个范围内选择最多整数 II 🔒		贪心 数组 二分查找 1+	🟠	🀄️ 🔗