448. 找到所有数组中消失的数字
题目描述
输入长度为 n 的整数数组 nums，每个元素都在 [1, n] 之间。有些值可能出现多次，于是另一些值就会缺席。
找出 1 到 n 中所有没在 nums 里出现过的数，以数组形式返回。返回顺序不限。
示例 1
输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6]
解释：1 到 8 中缺少 5 和 6。
示例 2
输入：nums = [1,1] 输出：[2]
解释：1 到 2 中缺少 2。
数据范围
n == nums.length1 <= n <= 10^51 <= nums[i] <= n
进阶：能否在 O(n) 时间内完成，且除返回的数组外不使用额外空间？
解题思路：正负号标记
用哈希集合记录出现过的数需要 O(n) 空间。因为值域是 [1, n]，可以让下标 v-1 的格子充当数字 v 的“存在标记”：第一遍扫描时，对每个 x 把 nums[|x|-1] 翻成负数。第二遍中仍是正数的格子 i，说明没有任何数指向它，数字 i+1 就缺失了。
为什么正确
第一遍结束后，nums[i] < 0 当且仅当 i+1 在原数组中出现过；绝对值始终保留原来的数。
复杂度分析
时间 O(n)，额外空间 O(1)（不计返回数组）。
易错点
不加判断地直接取反 nums[i] = -nums[i]：重复的数会把格子翻回正数，误判为缺失。应只在它是正数时翻转（或写成 -abs(nums[i])）。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
for x in nums:
i = abs(x) - 1
if nums[i] > 0:
nums[i] = -nums[i]
return [i + 1 for i, x in enumerate(nums) if x > 0]class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int x : nums) {
int i = Math.abs(x) - 1;
if (nums[i] > 0) {
nums[i] = -nums[i];
}
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++)
if (nums[i] > 0) res.add(i + 1);
return res;
}
}class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for (int x : nums) {
int i = abs(x) - 1;
if (nums[i] > 0) {
nums[i] = -nums[i];
}
}
vector<int> res;
for (int i = 0; i < (int)nums.size(); i++)
if (nums[i] > 0) res.push_back(i + 1);
return res;
}
};func findDisappearedNumbers(nums []int) []int {
for _, x := range nums {
if x < 0 {
x = -x
}
i := x - 1
if nums[i] > 0 {
nums[i] = -nums[i]
}
}
res := []int{}
for i, x := range nums {
if x > 0 {
res = append(res, i+1)
}
}
return res
}var findDisappearedNumbers = function(nums) {
for (const x of nums) {
const i = Math.abs(x) - 1;
if (nums[i] > 0) {
nums[i] = -nums[i];
}
}
const res = [];
nums.forEach((x, i) => { if (x > 0) res.push(i + 1); });
return res;
};function findDisappearedNumbers(nums: number[]): number[] {
for (const x of nums) {
const i = Math.abs(x) - 1;
if (nums[i] > 0) {
nums[i] = -nums[i];
}
}
const res: number[] = [];
nums.forEach((x, i) => { if (x > 0) res.push(i + 1); });
return res;
}其他解法
两种方法都把原数组当哈希表；正负号标记更短，交换归位更通用，能同时找出重复数和缺失数。
解法 2：原地交换归位 时间 O(n)，空间 O(1)
把每个数 x 交换到下标 x−1 上，直到当前位置的数已在正确位置或目标位置已有相同的数。完成后，凡是 nums[i] ≠ i+1 的位置 i，数字 i+1 就没有出现过。
和第 442、41 题的思路通用。交换过程需要用均摊分析才能看出是 O(n)。
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
n = len(nums)
# 把每个数 x 换到下标 x-1 上
for i in range(n):
while nums[i] != nums[nums[i] - 1]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
return [i + 1 for i in range(n) if nums[i] != i + 1]class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] != nums[nums[i] - 1]) {
int j = nums[i] - 1;
int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) if (nums[i] != i + 1) ans.add(i + 1);
return ans;
}
}class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
while (nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]);
}
vector<int> ans;
for (int i = 0; i < n; i++) if (nums[i] != i + 1) ans.push_back(i + 1);
return ans;
}
};func findDisappearedNumbers(nums []int) []int {
n := len(nums)
for i := 0; i < n; i++ {
for nums[i] != nums[nums[i]-1] {
j := nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
}
}
ans := []int{}
for i := 0; i < n; i++ {
if nums[i] != i+1 {
ans = append(ans, i+1)
}
}
return ans
}var findDisappearedNumbers = function(nums) {
const n = nums.length;
for (let i = 0; i < n; i++) {
while (nums[i] !== nums[nums[i] - 1]) {
const j = nums[i] - 1;
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
const ans = [];
for (let i = 0; i < n; i++) if (nums[i] !== i + 1) ans.push(i + 1);
return ans;
};function findDisappearedNumbers(nums: number[]): number[] {
const n = nums.length;
for (let i = 0; i < n; i++) {
while (nums[i] !== nums[nums[i] - 1]) {
const j = nums[i] - 1;
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
const ans: number[] = [];
for (let i = 0; i < n; i++) if (nums[i] !== i + 1) ans.push(i + 1);
return ans;
}