Leetcode-645-错误的集合

题目描述

• 集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
• 给定一个数组 nums 代表了集合 S 发生错误后的结果。
• 请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1：

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

示例 2：

输入：nums = [1,1]
输出：[1,2]

方法一 ： 哈希表

• 重复的数字在数组中出现 2次，丢失的数字在数组中出现 0次，其余的每个数字在数组中出现 1 次。
  • 因此可以使用哈希表记录每个元素在数组中出现的次数
  • 然后遍历从 1 到 n 的每个数字，分别找到出现 2 次和出现 0 次的数字，即为重复的数字和丢失的数字。

class Solution {
    public int[] findErrorNums(int[] nums) {
        // 1. 创建哈希表并且把数组塞入
        int n = nums.length;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0) + 1);
        }

        // 2. 遍历哈希表，统计重复和缺失的元素
        int[] result = new int[2];
        for(int i = 1;i <= n;i++){
            int count = map.getOrDefault(i,0);
            if(count == 2){
                result[0] = i;
            }else if(count == 0){
                result[1] = i;
            }
        }
        return result;
    }
}

复杂度分析：

• 时间复杂度 : O(n), 遍历数组和哈希表的时间
• 空间复杂度 ：O(n)，哈希表使用的空间

打赏