题目描述

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。

给定一个数组 nums 代表了该集合发生错误后的结果。找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例：输入 nums = [1,2,2,4]，输出 [2,3]。其中 2 是重复的数字，3 是丢失的数字。

解题思路

本题本质上是在 1 到 n 这 n 个数字中，有一个数字出现了两次，有一个数字没有出现。我们需要找出这两个数字。

方法：计数数组

因为数组中的数字都在 [1, n] 范围内，我们可以使用一个长度为 n 的辅助数组（或直接在原数组上标记）来统计每个数字出现的次数。

  1. 创建一个长度为 n 的数组 res，初始值全为 0。
  2. 遍历 nums，对于每个数字 num，将 res[num - 1] 的值加 1。
  3. 再次遍历 res（或遍历 1 到 n）：
    • 如果 res[i] == 0，说明数字 i + 1 没有出现过，即丢失的数字。
    • 如果 res[i] == 2，说明数字 i + 1 出现了两次，即重复的数字。
  4. 返回 [重复数字, 丢失数字]。

为什么这是正确的？

每个数字理论上应该恰好出现一次。由于只有”一个重复、一个丢失”，统计完频次后，出现 0 次的必然是丢失的数字，出现 2 次的必然是重复的数字。其余数字出现次数均为 1。

这个方法的巧妙之处在于利用了数字范围和数组下标的对应关系，将数字本身映射到索引上作为计数槽位。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组长度。需要两次遍历，每次遍历都是 O(n)。
  • 空间复杂度：O(n)，使用了一个大小为 n 的计数数组。

进阶：如果想达到 O(1) 额外空间，可以通过在原数组上用”取负数标记”或”异或运算”来实现，但上述计数法最为直观易懂。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package code.J645;

public class J645 {
    public int[] findErrorNums(int[] nums) {
        int errorNum = 0, notFoundNum = 0;
        int[] res = new int[nums.length];
        for (int num : nums) {
            res[num - 1]++;
        }
        for (int i = 0; i < nums.length; i++) {
            if (res[i] == 0) notFoundNum = i + 1;
            if (res[i] == 2) errorNum = i + 1;
        }
        return new int[]{errorNum, notFoundNum};
    }
}