LC 645. 错误的集合

题目描述

这是 LeetCode 上的 645. 错误的集合 ，难度为 简单。

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

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1：

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

示例 2：
1
2
输入：nums = [1,1]
输出：[1,2]

提示：

  • 2 <= nums.length <= $10^4$
  • 1 <= nums[i] <= $10^4$

计数

一个朴素的做法是，使用「哈希表」统计每个元素出现次数，然后在 $[1, n]$ 查询每个元素的出现次数。

在「哈希表」中出现 $2$ 次的为重复元素，未在「哈希表」中出现的元素为缺失元素。

由于这里数的范围确定为 $[1, n]$，我们可以使用数组来充当「哈希表」，以减少「哈希表」的哈希函数执行和冲突扩容的时间开销。

image.png

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int[] cnts = new int[n + 1];
        for (int x : nums) cnts[x]++;
        int[] ans = new int[2];
        for (int i = 1; i <= n; i++) {
            if (cnts[i] == 0) ans[1] = i;
            if (cnts[i] == 2) ans[0] = i;
        }
        return ans;
    }
}

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

数学

我们还可以利用数值范围为 $[1, n]$，只有一个数重复和只有一个缺失的特性，进行「作差」求解。

  • 令 $[1, n]$ 的求和为 $tot$，这部分可以使用「等差数列求和公式」直接得出：$tot = \frac{n (1 + n)}{2}$ ；
  • 令数组 $nums$ 的求和值为 $sum$，由循环累加可得；
  • 令数组 $sums$ 去重求和值为 $set$，由循环配合「哈希表/数组」累加可得。

最终答案为 (重复元素, 缺失元素) = (sum-set, tot-set) 。

image.png

代码；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int[] cnts = new int[n + 1];
        int tot = (1 + n) * n / 2;
        int sum = 0, set = 0;
        for (int x : nums) {
            sum += x;
            if (cnts[x] == 0) set += x;
            cnts[x] = 1;
        }
        return new int[]{sum - set, tot - set};
    }
}

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

桶排序

因为值的范围在 $[1, n]$，我们可以运用「桶排序」的思路，根据 $nums[i] = i + 1$ 的对应关系使用 $O(n)$ 的复杂度将每个数放在其应该落在的位置里。

然后线性扫描一遍排好序的数组，找到不符合 $nums[i] = i + 1$ 对应关系的位置，从而确定重复元素和缺失元素是哪个值。

image.png

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        int a = -1, b = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                a = nums[i];
                b = i == 0 ? 1 : nums[i - 1] + 1;
            }
        }
        return new int[]{a, b};
    }
    void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.645 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。