LeetCode 645. 错误的集合
题目描述
题意分析
长度为 $n$ 的数组原本应包含 $1$ 到 $n$ 各一次，现在其中一个数被改成了另一个已有的数。找出重复值与缺失值，并按这个顺序返回；数组不保证有序。
解法：计数数组
核心思路
[!blue]
先按值统计出现次数，再找偏离一次的两个值。 一次替换使原值从出现一次变成零次，目标值从出现一次变成两次，其余值不变。因此频次为 2 的就是重复值，频次为 0 的就是缺失值，两者都唯一。合法值域是 $[1,n]$，可以直接创建长度为 $n+1$ 的计数数组，让
cnt[v]表示数字 $v$ 的频次；下标 0 不使用。遍历全部输入后，再扫描 $1$ 到 $n$，分别把频次为 2 和 0 的下标记录为dup、missing。缺失判断必须等统计结束后再做，否则暂时没读到的数字也会被误认为缺失。按值计数不依赖输入顺序，也不需要修改数组。最后返回
[dup, missing]，顺序由题意规定，与两个值谁大谁小无关。
解题步骤
- 创建 n+1 长度的频次数组。
- 遍历输入，按数值增加频次。
- 扫描 1 到 n，分别记录频次二和零的位置。
- 按规定顺序返回两值。
代码实现
class Solution {
public int[] findErrorNums(int[] nums) {
int n = nums.length;
int[] cnt = new int[n + 1];
for (int x : nums) {
cnt[x]++;
}
int dup = -1;
int missing = -1;
// 只扫描合法值域，频次二与零分别对应重复值和缺失值。
for (int i = 1; i <= n; i++) {
if (cnt[i] == 2) {
dup = i;
} else if (cnt[i] == 0) {
missing = i;
}
}
return new int[] {
dup,
missing
};
}
}
func findErrorNums(nums []int) []int {
n := len(nums)
count := make([]int, n+1)
for _, num := range nums {
count[num]++
}
dup, missing := -1, -1
// 只扫描合法值域，频次二与零分别对应重复值和缺失值。
for i := 1; i <= n; i++ {
if count[i] == 2 {
dup = i
} else if count[i] == 0 {
missing = i
}
}
return []int{
dup,
missing,
}
}
复杂度分析
- 时间复杂度：$O(n)$，统计和查找各一遍。
- 空间复杂度：$O(n)$，频次数组。
关键点总结
[!green]
- 值域和数组下标直接对应。
- 频次统计同时服务重复和缺失两个答案。
- 缺失值需要在完整统计后判断。
易错点总结
[!yellow]
- 只开 n 项且直接按值索引：值 n 会越界。
- 发现重复就立即返回：缺失值尚未确定。
- 只用实际和减理想和：仅得到两者差，不能独立确定两个值。
- 交换返回顺序：不符合接口要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 268. 丢失的数字 | 简单 | 原题只缺一个数，本题还多一个重复值，需要同时还原两个异常值。 |
| 442. 数组中重复的数据 | 中等 | 同样可利用1到n的下标映射识别重复，本题还要找缺失位置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！