【C++刷题】力扣-#645-错误的集合

题目描述

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

示例

示例 1

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

示例 2

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

题解

这个问题可以通过遍历数组并使用哈希表来记录已经出现过的数字来解决。

1. 初始化哈希表：创建一个哈希表 countMap 来统计 nums 中每个数字的出现次数。
2. 统计出现次数：遍历 nums，更新 countMap 中的计数。
3. 找出重复的数字：遍历 countMap，找出出现次数为2的数字。
4. 找出丢失的数字：遍历 countMap，找出没有出现的数字（即出现次数为0的数字）。
5. 返回结果：返回一个包含重复数字和丢失数字的数组。

代码实现

vector<int> findErrorNums(vector<int>& nums) {
    unordered_map<int, int> countMap;
    for (int num : nums) {
        countMap[num]++;
    }

    int duplicate = -1;
    int missing = -1;
    for (int i = 1; i <= nums.size(); ++i) {
        if (countMap[i] == 0) {
            missing = i;
        }
        if (countMap[i] == 2) {
            duplicate = i;
        }
    }
    return {duplicate, missing};
}

复杂度分析

● 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们需要遍历一次数组。
● 空间复杂度：O(n)，用于存储哈希表。
这个算法通过使用哈希表来记录已经出现过的数字，可以快速地找到错位的数字。