六安商城网站建设地址,华为网站建设目标,陕西省高速建设集团网站,保定网站制作套餐❓645. 错误的集合
难度#xff1a;简单
集合 s 包含从 1 到 n 的整数。不幸的是#xff0c;因为数据错误#xff0c;导致集合里面某一个数字复制了成了集合里面的另外一个数字的值#xff0c;导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了…❓645. 错误的集合
难度简单
集合 s 包含从 1 到 n 的整数。不幸的是因为数据错误导致集合里面某一个数字复制了成了集合里面的另外一个数字的值导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数再找到丢失的整数将它们以数组的形式返回。
示例 1 输入nums [1,2,2,4] 输出[2,3] 示例 2 输入nums [1,1] 输出[1,2] 提示 2 n u m s . l e n g t h 1 0 4 2 nums.length 10^4 2nums.length104 1 n u m s [ i ] 1 0 4 1 nums[i] 10^4 1nums[i]104
思路
法一交换数组元素
最直接的方法是先对数组进行排序这种方法时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。本题可以以 O ( n ) O(n) O(n) 的时间复杂度、 O ( 1 ) O(1) 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:vectorint findErrorNums(vectorint 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(vectorint nums, int i, int j){int tmp nums[i];nums[i] nums[j];nums[j] tmp;}
};法二哈希表 Java
class Solution {public int[] findErrorNums(int[] nums) {HashSetInteger 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:vectorint findErrorNums(vectorint nums) {unordered_setint 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 ) O(n) O(n)其中 n 为数组的长度。空间复杂度 O ( 1 ) O(1) O(1)法一只需常量级空间而哈希表需要创建大小为 O ( n ) O(n) O(n) 的哈希表空间复杂度为 O ( n ) O(n) O(n)。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我 leetCode专栏每日更新 注 如有不足欢迎指正
