LeetCode 448: Find All Numbers Disappeared in an Array (In-Place Sign Marking on Value-Mapped Indices)
LeetCode 448ArrayIn-Place HashingToday we solve LeetCode 448 - Find All Numbers Disappeared in an Array.
Source: https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/
English
Problem Summary
Given an array nums of length n, where each value is in [1, n], some numbers appear once and some appear twice. Return all numbers in [1, n] that do not appear in nums.
Key Insight
Each value x should map to index x - 1. If x appears, mark nums[x - 1] as negative. After marking all values, indices that remain positive correspond to missing numbers.
Brute Force and Why Insufficient
Using a hash set is straightforward: insert all elements, then scan 1..n and pick missing ones. It works in O(n) time but needs extra O(n) space. The in-place sign-marking method keeps extra space to O(1) (excluding output list).
Optimal Algorithm (Step-by-Step)
1) Traverse array, read v = abs(nums[i]).
2) Convert to index idx = v - 1.
3) Set nums[idx] = -abs(nums[idx]) to mark "seen".
4) Traverse again: if nums[i] > 0, then i + 1 is missing.
5) Collect and return all such numbers.
Complexity Analysis
Time: O(n).
Space: O(1) extra (excluding output).
Common Pitfalls
- Forgetting abs() when reading values after signs have changed.
- Overwriting with plain negative without abs, causing accidental sign flips.
- Returning indices directly instead of i + 1.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int v = Math.abs(nums[i]);
int idx = v - 1;
nums[idx] = -Math.abs(nums[idx]);
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) ans.add(i + 1);
}
return ans;
}
}func findDisappearedNumbers(nums []int) []int {
abs := func(x int) int {
if x < 0 {
return -x
}
return x
}
for i := 0; i < len(nums); i++ {
v := abs(nums[i])
idx := v - 1
nums[idx] = -abs(nums[idx])
}
ans := make([]int, 0)
for i := 0; i < len(nums); i++ {
if nums[i] > 0 {
ans = append(ans, i+1)
}
}
return ans
}class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for (int i = 0; i < (int)nums.size(); ++i) {
int v = abs(nums[i]);
int idx = v - 1;
nums[idx] = -abs(nums[idx]);
}
vector<int> ans;
for (int i = 0; i < (int)nums.size(); ++i) {
if (nums[i] > 0) ans.push_back(i + 1);
}
return ans;
}
};class Solution:
def findDisappearedNumbers(self, nums: list[int]) -> list[int]:
for i in range(len(nums)):
v = abs(nums[i])
idx = v - 1
nums[idx] = -abs(nums[idx])
ans: list[int] = []
for i in range(len(nums)):
if nums[i] > 0:
ans.append(i + 1)
return ansvar findDisappearedNumbers = function(nums) {
const abs = (x) => (x < 0 ? -x : x);
for (let i = 0; i < nums.length; i++) {
const v = abs(nums[i]);
const idx = v - 1;
nums[idx] = -abs(nums[idx]);
}
const ans = [];
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) ans.push(i + 1);
}
return ans;
};中文
题目概述
给你一个长度为 n 的数组 nums，元素取值范围都在 [1, n]。有些数字出现一次，有些出现两次。请找出 [1, n] 中没有出现在数组里的所有数字。
核心思路
把“值”映射到“下标”：值 x 对应下标 x - 1。遍历数组时，看到值 x 就把 nums[x - 1] 标记为负数。最后仍为正数的位置，说明该值从未出现。
朴素解法与不足
朴素做法是用哈希集合记录出现过的数字，再扫描 1..n 找缺失值。时间是 O(n)，但额外空间也是 O(n)。本题可用原地标记把额外空间降到 O(1)（不计返回数组）。
最优算法（步骤）
1）遍历数组，读取 v = abs(nums[i])。
2）映射到下标 idx = v - 1。
3）执行 nums[idx] = -abs(nums[idx])，标记该值出现过。
4）第二次遍历，若 nums[i] > 0，则 i + 1 缺失。
5）收集并返回所有缺失数字。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)（额外空间，不计输出）。
常见陷阱
- 标记后再读值时忘记取绝对值。
- 直接写负号而不加 abs，可能把已标记位置误翻回正数。
- 返回时误把下标当答案，正确值应为 i + 1。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int v = Math.abs(nums[i]);
int idx = v - 1;
nums[idx] = -Math.abs(nums[idx]);
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) ans.add(i + 1);
}
return ans;
}
}func findDisappearedNumbers(nums []int) []int {
abs := func(x int) int {
if x < 0 {
return -x
}
return x
}
for i := 0; i < len(nums); i++ {
v := abs(nums[i])
idx := v - 1
nums[idx] = -abs(nums[idx])
}
ans := make([]int, 0)
for i := 0; i < len(nums); i++ {
if nums[i] > 0 {
ans = append(ans, i+1)
}
}
return ans
}class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for (int i = 0; i < (int)nums.size(); ++i) {
int v = abs(nums[i]);
int idx = v - 1;
nums[idx] = -abs(nums[idx]);
}
vector<int> ans;
for (int i = 0; i < (int)nums.size(); ++i) {
if (nums[i] > 0) ans.push_back(i + 1);
}
return ans;
}
};class Solution:
def findDisappearedNumbers(self, nums: list[int]) -> list[int]:
for i in range(len(nums)):
v = abs(nums[i])
idx = v - 1
nums[idx] = -abs(nums[idx])
ans: list[int] = []
for i in range(len(nums)):
if nums[i] > 0:
ans.append(i + 1)
return ansvar findDisappearedNumbers = function(nums) {
const abs = (x) => (x < 0 ? -x : x);
for (let i = 0; i < nums.length; i++) {
const v = abs(nums[i]);
const idx = v - 1;
nums[idx] = -abs(nums[idx]);
}
const ans = [];
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) ans.push(i + 1);
}
return ans;
};
Comments