( 数组和矩阵) 645. 错误的集合 ——【Leetcode每日一题】

❓645. 错误的集合

难度：简单

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

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

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

示例 1：

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

示例 2：

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

提示：

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

💡思路：

法一：交换数组元素

最直接的方法是先对数组进行排序，这种方法时间复杂度为 $O(nlogn)$。本题可以以 $O(n)$ 的时间复杂度、$O(1)$ 空间复杂度来求解。

• 主要思想是通过交换数组元素，使得数组上的元素在正确的位置上；
• 这样只有 重复的数 出现在 丢失整数 的位置上。

法二：哈希表

重复的数字在数组中出现 2 次，丢失的数字在数组中出现 0次，其余的每个数字在数组中出现 1 次。因此可以使用哈希表记录每个元素在数组中是否出现

• 如果出现两次，则找到了重复的数；
• 将所有数都存到哈希表，再遍历哈希表，则可找到丢失的数；

🍁代码：(Java、C++)

法一：交换数组元素
Java

class Solution {public int[] findErrorNums(int[] nums) {for(int i = 0; i < nums.length; i++){while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){swap(nums, i, nums[i] - 1);}}for(int i = 1; i <= nums.length; i++){if(nums[i - 1] != i){return new int[]{nums[i - 1], i};}}return null;}private void swap(int[] nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

C++

class Solution {
public:vector<int> findErrorNums(vector<int>& nums) {for(int i = 0; i < nums.size(); i++){while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){swap(nums, i, nums[i] - 1);}}for(int i = 1; i <= nums.size(); i++){if(nums[i - 1] != i){return {nums[i - 1], i};}}return {};}void swap(vector<int>& nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
};

法二：哈希表
Java

class Solution {public int[] findErrorNums(int[] nums) {HashSet<Integer> s = new HashSet<>();int repeat = 0, lose = 0;for(int num : nums){if(s.contains(num)) repeat = num;s.add(num);}for(int i = 1; i <= nums.length; i++){if(!s.contains(i)){lose = i;break;}}return new int[]{repeat, lose};}
}

C++

class Solution {
public:vector<int> findErrorNums(vector<int>& nums) {unordered_set<int> s;int repeat = 0, lose = 0;for(int num : nums){if(s.find(num) != s.end()) repeat = num;s.insert(num);}for(int i = 1; i <= nums.size(); i++){if(s.find(i) == s.end()){lose = i;break;}}return {repeat, lose};}
};

🚀 运行结果：

🕔 复杂度分析：

• 时间复杂度：$O(n)$，其中 n 为数组的长度。
• 空间复杂度：$O(1)$，法一只需常量级空间；而哈希表需要创建大小为 $O(n)$ 的哈希表，空间复杂度为$O(n)$。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！

注： 如有不足，欢迎指正！