目标:查找出两个只出现一次的数字,其他数字都出现两次。
要求:时间复杂度O(n),空间复杂度O(1)。
1.起始代码(这里使用了哈希表,不符合题目要求)
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
vector<int>ans;
map<int,int>m;
for(auto x:nums){
m[x]++;
}
for(auto y:m){
if(y.second==1){
ans.push_back(y.first);
}
}
return ans;
}
};
2.优化后的分组异或代码
知识点:相同数字异或等于0。
算法流程:
1)遍历nums执行异或,记录n=x^y;
2)循环左移m,m记录第1次x和y二进制不同的位置;
3)根据m记录的位置,拆分nums为两组;
4)这两组相互异或分别得到所求的两个数字。
5)返回这两个数字。
参考:剑指 Offer 56 - I. 数组中数字出现的次数(位运算,清晰图解)
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int m=0,n=1,x=0,y=0;
for(auto num:nums){
m^=num;
}
while(!(m&n)){
n<<=1;
}
for(auto num:nums){
if(n&num){
x^=num;
}
else{
y^=num;
}
}
return {x,y};
}
};