❓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 2<=nums.length<=104
- 1 < = n u m s [ i ] < = 1 0 4 1 <= nums[i] <= 10^4 1<=nums[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:
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
)
O(n)
O(n),其中
n
为数组的长度。 - 空间复杂度: O ( 1 ) O(1) O(1),法一只需常量级空间;而哈希表需要创建大小为 O ( n ) O(n) O(n) 的哈希表,空间复杂度为 O ( n ) O(n) O(n)。
题目来源:力扣。文章来源:https://www.toymoban.com/news/detail-440959.html
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-440959.html
注: 如有不足,欢迎指正!
到了这里,关于( 数组和矩阵) 645. 错误的集合 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!