LeetCode645 错误的集合

发表于

这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战。

题目描述：

645. 错误的集合 - 力扣（LeetCode） (leetcode-cn.com)

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

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

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

示例一

1
2
ini复制代码输入： nums = [1,2,2,4]
输出： [2,3]

示例二

1
2
ini复制代码输入： nums = [1,1]
输出： [1,2]

提示：

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

思路分析

排序

这个比较简单，排序之后，每每比较相邻元素，如果相等，说明为重复元素，至于丢失的元素也很好找，我们只要注意一下开头和结尾的边界情况即可。

哈希表

根据题意，这本是一个1到n的数组，现在丢失了一个数字，变成了一个重复的数字，结果一定是重复的数组是2个，丢失的数组是0个。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Java复制代码class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] errorNums = new int[2];
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int i = 1; i <= n; i++) {
            int count = map.getOrDefault(i, 0);
            if (count == 2) {
                errorNums[0] = i;
            } else if (count == 0) {
                errorNums[1] = i;
            }
        }
        return errorNums;
    }
}

总结

虽然是一道简单的题，但是解法多多，除了上面的2个之外，官方还有位运算的解法，三叶姐也有多种其他解法，学海无涯。

参考

645. 错误的集合 题解 - 力扣（LeetCode） (leetcode-cn.com)

【宫水三叶】一题三解：「计数」&「数学」&「桶排序」 - 错误的集合 - 力扣（LeetCode） (leetcode-cn.com)

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%