跳到主要内容

645. 错误的集合

1. 题目简介​

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

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

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

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

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

2.1 问题分析​

用布尔数组 arr 记录每个数字是否出现过，就能分别找到重复值和缺失值。arr[num] 为 true 表示已经遇到过 num，因此数组申请 n + 1 个位置，下标 0 不使用。

先扫描 nums。第一次遇到某个数字时，把它对应的位置设为 true；再次遇到时，这个数字就是 duplicate。扫描结束后，再检查 arr[1] 到 arr[n]，仍为 false 的位置就是缺失数字 absent。

例如 [1, 2, 2, 4] 中，第二次遇到 2 时能确定重复值；扫描完发现 arr[3] 仍为 false，因此返回 [2, 3]。

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 问题分析​

把数字 t 放到下标 t - 1，就能利用原数组记录数字是否出现。例如 1 放到下标 0，2 放到下标 1，不再需要布尔数组。

遍历到 nums[i] 时，如果它不等于 i + 1，就把它交换到目标下标 nums[i] - 1。换回来的数字也可能放错了位置，因此要继续检查，直到当前位置正确，或目标位置已经保存了相同数字。后一种情况必须停止，否则两个重复数字会不断交换。

处理完后，唯一没有放对的位置对应缺失值：下标 i 应该保存 i + 1，实际却保存了多出来的重复值 nums[i]。例如 [1, 2, 2, 4] 的下标 2 应该是 3，却是 2，因此返回重复值 2 和缺失值 3。

这种方法会修改输入数组。第一种方法保留输入、使用 O(n) 额外空间；第二种方法通过交换省下这部分空间，可以根据是否允许修改输入来选择。

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)。每次有效交换至少让一个数字归位，归位后不会再被移走，因此交换总次数不超过 n；最后再扫描一次找出不匹配的位置。
  • 空间复杂度：O(1)，仅使用了常数级别的空间。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明