跳到主要内容

645. 错误的集合

1. 题目简介​

难度：简单，原题链接：645. 错误的集合。

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

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

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

2. 解法一：使用额外空间记录数字是否出现​

2.1. 问题分析​

难度为简单的话，先使用比较直接的算法吧。

1 到 n 中有一个数字重复，一个数字没有出现。遍历 1 到 n 时，我们可以记录每一个数字是否出现，如果出现了两次，那么就是重复的数字；如果没有出现，那么就是缺失的数字。

记录数字是否出现的方式有很多，为了使空间占用的少一些，我们使用一个 boolean[] 数组来记录数字是否出现。

2.2. 代码实现​

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        boolean[] arr = new boolean[n + 1];
        int duplicate = -1;
        for (int num : nums) {
            if (arr[num]) {
                duplicate = num;
            } else {
                arr[num] = true;
            }
        }
        int absent = -1;
        for (int i = 1; i <= n; i++) {
            if (!arr[i]) {
                absent = i;
                break;
            }
        }
        return new int[]{duplicate, absent};
    }
}

2.3. 复杂度分析​

  • 时间复杂度：O(n)，需要遍历数组。
  • 空间复杂度：O(n)，使用了额外的 boolean[] 来记录数字是否出现。

3. 解法二：将元素放到正确的位置​

在上面的直接解法中，使用了额外的空间，虽然可以通过官方的测试用例，但是是否有不使用额外空间的解法呢？

3.1 问题分析​

题目中给出的数组是 1 到 n 的排列，抛开缺失与重复的元素后，剩下的元素按照循序排序，对于 1 <= t <= n，t 在数组中的位置应该是 i = t - 1。

基于上面的思路，我们可以遍历数组，对于每一个元素 num，将其放到正确的位置 num - 1，如果 num 已经在正确的位置上，那么就不需要交换。

需要注意的是，对于重复元素，需要做额外的特殊处理，如果发现目标位置的元素与当前元素相等，那么不做交换直接跳过。

将所有元素都放到「正确」的位置后，再次遍历数组，找到第一个不在正确位置上的元素，这个元素就是重复的元素，而缺失的元素就是 i + 1。

PS：虽然这种方法没有使用额外的空间，但是在官方用例下，执行时间要 慢 于第一种解法，写起来也麻烦很多，如果没有特殊要求，直接使用第一种写法即可。

3.2. 代码实现​

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;
    }
}

3.3. 复杂度分析​

  • 时间复杂度：O(n)，需要遍历数组。
  • 空间复杂度：O(1)，仅使用了常数级别的空间。