LeetCode645-错误的集合

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/set-mismatch/

中文链接：https://leetcode-cn.com/problems/set-mismatch/

题目详述

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

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

示例 1:

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

注意:

  1. 给定数组的长度范围是 [2, 10000]。
  2. 给定的数组是无序的。

题目详解

  • 创建一个 boolean 数组 vis，用来记录 1~n 的数是否出现过。
  • 遍历数组，将 vis 对应位置设置为 true，代表出现过。
  • 若在遍历过程中，发现 vis 对应位置已经为 true，说明此元素重复出现。
  • 最后遍历 vis 数组，为 false 的位置表示丢失的那个数。
  • 时间复杂度为 O(n)。
  • 空间复杂度为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_00645 {

    public int[] findErrorNums(int[] nums) {
        boolean[] vis = new boolean[nums.length + 1];
        int[] res = new int[2];
        for (int num : nums) {
            if (vis[num]) {
                res[0] = num;
            } else {
                vis[num] = true;
            }
        }
        for (int i = 1; i < vis.length; ++i) {
            if (!vis[i]) {
                res[1] = i;
                break;
            }
        }
        return res;
    }
}
  • 遍历数组，将元素映射到的位置的元素变为它的相反数。
  • 在遍历过程中，当元素映射到的位置的元素为负数，说明这个位置重复出现。
  • 最后遍历数组，发现某个位置的元素大于 0，说明这个位置表示丢失的那个数。
  • 这种方法会修改原数组，不过我们最后可以将数组还原。
  • 时间复杂度为 O(n)。
  • 空间复杂度为 O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_00645 {

    public int[] findErrorNums(int[] nums) {
        int[] res = new int[2];
        for (int num : nums) {
            if (nums[Math.abs(num) - 1] < 0) {
                res[0] = Math.abs(num);
            } else {
                nums[Math.abs(num) - 1] *= -1;
            }
        }
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] > 0) {
                res[1] = i + 1;
                break;
            }
        }
        return res;
    }
}
  • 运用位运算。
  • 将 1~n 所有数与数组中的所有数进行异或，得到的结果是重复的数与丢失的数的异或值，记为 t。
  • 根据这个异或值 t 得到它最后一个 1 代表的数，根据这个数来进行分组。可以把数分为两组，一组对应二进制位为 0，进行 & 运算之后为 0；另一组对应二进制位为 1，进行 & 运算之后不为 0。
  • 将 1~n 所有数与数组中的所有数按照上述分组方式进行异或，得到的两个值就代表重复的数和丢失的数。
  • 最后遍历原数组确定哪个是重复的数即可，另一个就是丢失的数。
  • 时间复杂度为 O(n)。
  • 空间复杂度为 O(1)。

位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class LeetCode_00645 {

    public int[] findErrorNums(int[] nums) {
        int t = 0;
        for (int i = 1; i <= nums.length; ++i) {
            t ^= i;
        }
        for (int num : nums) {
            t ^= num;
        }
        int lastOne = t & -t;	// 得到最后一个 1
        int t1 = 0, t2 = 0;
        for (int i = 1; i <= nums.length; ++i) {
            if ((i & lastOne) == 0) {
                t1 ^= i;
            } else {
                t2 ^= i;
            }
        }
        for (int num : nums) {
            if ((num & lastOne) == 0) {
                t1 ^= num;
            } else {
                t2 ^= num;
            }
        }
        for (int num : nums) {
            if (num == t1) {
                return new int[]{t1, t2};
            }
        }
        return new int[]{t2, t1};
    }
}