题目:
集合 s 包含从 1 到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合丢失了一个数字并且有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/set-mismatch
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
示例:
示例 1:
输入:nums = [1,2,2,4]
输出:[2,3]
示例 2:
输入:nums = [1,1]
输出:[1,2]
提示:
2 <= nums.length <= 10^4
1 <= nums[i] <= 10^4
个人代码如下:
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> newnums;//用来返回最终结果
sort(nums.begin(),nums.end());//利用sort函数对数组进行排序
int number = 1;//用来进行数组数字顺序比对,初始值设为1
//本层循环用来找到相同的重复数
for(int i=0;i<nums.size()-1;i++){
if(nums[i] == nums[i+1]){
newnums.push_back(nums[i]);//将当前的数组元素存入返回结果的新数组中
nums.erase(nums.begin()+i,nums.begin()+i+1);//利用erase函数删除下一个相同元素
break;//数组只有一个重复数,找到后即可退出循环
}
/*nums.erase(nums.begin()+i,nums.begin()+i+1);
break;*/
}
//本层循环用来找到不匹配的元素
for(int i=0;i<nums.size()+1;i++){
if(nums[i] != number){
newnums.push_back(number);//将与数组元素不匹配的number插入到新数组中,即为丢失元素
break;//只有一个不匹配元素,找到即可退出循环
}
number ++;//若数组元素与number相等,则number自增1继续循环
}
return newnums;
}
};
解题思路:
如代码注释。
官方哈希表方法代码如下:
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> errorNums(2);
int n = nums.size();
unordered_map<int, int> mp;
for (auto& num : nums) {
mp[num]++;
}
for (int i = 1; i <= n; i++) {
int count = mp[i];
if (count == 2) {
errorNums[0] = i;
} else if (count == 0) {
errorNums[1] = i;
}
}
return errorNums;
}
};
解题思路:
重复的数字在数组中出现 2 次,丢失的数字在数组中出现 0 次,其余的每个数字在数组中出现 1 次。因此可以使用哈希表记录每个元素在数组中出现的次数,然后遍历从 1 到 n 的每个数字,分别找到出现 2 次和出现 0 次的数字,即为重复的数字和丢失的数字。