错误的集合
集合 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\)
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/set-mismatch
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路1:哈希表
这个没啥好说的。
code
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int n = nums.size();
vector<int> cnt(n + 1,0);
for(auto item : nums) cnt[item] ++;
vector<int> ans(2,0);
for(int i = 1;i <= n;i ++)
{
if(cnt[i] == 0) ans[1] = i;
if(cnt[i] == 2) ans[0] = i;
}
return ans;
}
};
位运算
为了在常数空间内实现,需要使用位运算,实际上像是这种出现偶数次的通常可以考虑使用异或消除,但是本文中出现偶数次的是重复的数字,也是最后的结果,我们并不希望消除掉,怎么办呢?
- 在数组中添加1-n,这样重复的数字和缺失的数字都是奇数次,其余数字都是偶数次
- 全部异或就可以将其余数字全部去除
- 记x为重复的数字,y为缺失的数字,最后的结果为x ^ y
- 如何在2n个数字中找到x和y呢
- lowbit(x ^ y)为x和y的最低不同位,根据最低不同位区分x和y,将2n个数字都分到两个不同的组别中,同时每个组中可以通过异或消除重复的数字,找到x和y
- 最后判别x和y哪个是重复的哪个是缺失的
code
class Solution {
public:
int lowbit(int x)
{
return x & (-x);
}
vector<int> findErrorNums(vector<int>& nums) {
int n = nums.size();
int xy = 0;
for(auto item : nums) xy = xy ^ item;
for(int i = 1;i <= n;i ++) xy = xy ^ i;
int diff = lowbit(xy);
int nums1 = 0,nums2 = 0;
for(auto item : nums)
{
if((item & diff) == 0) nums1 ^= item;
else nums2 ^= item;
}
for(int i = 1;i <= n;i ++)
{
if((i & diff) == 0) nums1 ^= i;
else nums2 ^= i;
}
for(auto item : nums)
{
if(item == nums1) return {nums1,nums2};
}
return {nums2,nums1};
}
};
标签:数字,错误,nums,int,重复,vector,645,集合
From: https://www.cnblogs.com/huangxk23/p/17288094.html