LC 645. 错误的集合

题目描述

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

集合 s 包含从 1 到 n 的整数。

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

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

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

示例 1：

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

输出：[2,3]

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

输出：[1,2]

提示：

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

计数

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

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

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

Java 代码：

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

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        vector<int> cnts(n + 1, 0), ans(2);
        for (int x : nums) cnts[x]++;
        for (int i = 1; i <= n; i++) {
            if (cnts[i] == 2) ans[0] = i;
            else if (cnts[i] == 0) ans[1] = i;
        }
        return ans;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        cnts, ans = [0] * (n + 1), [0, 0]
        for x in nums:
            cnts[x] += 1
        for i in range(1, n + 1):
            if cnts[i] == 2:
                ans[0] = i
            elif cnts[i] == 0:
                ans[1] = 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) 。

Java 代码：

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

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size(), tot = (1 + n) * n / 2, sumv = 0, setv = 0;
        vector<int> cnts(n + 1, 0);
        for (int x : nums) {
            sumv += x;
            if (cnts[x] == 0) setv += x;
            cnts[x] = 1;
        }
        return {sumv - setv, tot - setv};
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        tot = (1 + n) * n // 2
        sumv, setv = 0, 0
        cnts = [0] * (n + 1)
        for x in nums:
            sumv += x
            if cnts[x] == 0:
                setv += x
            cnts[x] = 1
        return [sumv - setv, tot - setv]

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

桶排序

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

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

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) swap(nums[i], nums[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 {a, b};
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n):
            while nums[i] != i + 1 and nums[nums[i] - 1] != nums[i]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
        a, b = -1, -1
        for i in range(n):
            if nums[i] != i + 1:
                a = nums[i]
                b = 1 if i == 0 else nums[i - 1] + 1
        return [a, b]

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

最后

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

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

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

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