LeetCode题目笔记——645. 错误的集合

题目描述

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

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

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

示例1：

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

示例2：

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

提示：

2 <= nums.length <= 104
1 <= nums[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/set-mismatch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目难度——简单

方法一：用哈希表

  既然题目说1到n中有一个缺失，有一个多了一次，那么我们就可以用一个字典来记录数组中每个数字出现的次数，然后出现次数为2和出现次数为0的就分别是想要的答案了。

代码/Python

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        res = [0, 0]
        table = dict(zip([x for x in range(1, len(nums) + 1)], [0] * len(nums)))
        for n in nums:
            table[n] += 1
            if table[n] == 2:
                res[0] = n
        
        for item in table.items():
            if item[1] == 0:
                res[1] = item[0]
        return res

代码/C++

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> res = {0, 0};
        int size = nums.size();
        unordered_map<int, int> table;
        for (auto n: nums){
            table[n]++;
        }
        for (int i = 1; i <= size; i++){
            if(table[i] == 2){
                res[0] = i;
            }
            if(table[i] == 0){
                res[1] = i;
            }
        }
        return res;
    }
};

  可以看到都挺慢的，可能是因为就算是哈希的运算只要1复杂度，但是多的运算也比较慢，所以我们可以用数组，数组更快。

方法二:使用数组

  xxx

代码

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int size = nums.size() + 1;
        vector<int> res = {0, 0};
        vector<int> arrays(size, 0);
        for (auto n: nums){
            arrays[n] += 1;
        }
        for (int i = 1; i < size; i++){
            if(arrays[i] == 2){
                res[0] = i;
            }
            if(arrays[i] == 0){
                res[1] = i;
            }
        }
        return res;
    }
};

  可以看到把数据结构换成数组之后，快了很多，所以有时候不必要用比较复杂的结构，简单的数组也能解决问题。

总结

  两种方法都要遍历两次，所以时间是O(N)，空间只用到了常数，所以也算是O(N)，第二种只用数组的方法比用哈希表的方法节省了10MB左右的空间，所以还是不错的。

最后

以上就是贪玩蜡烛为你收集整理的LeetCode题目笔记——645. 错误的集合的全部内容，希望文章能够帮你解决LeetCode题目笔记——645. 错误的集合所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。