排序 + 位运算
题目要求时间复杂度O(n),空间O(1);
排序代码
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
sort(nums.begin(), nums.end());
int len = nums.size();
vector<int> res(2);
int idx = 0, i = 0, j = 1;
for(; j < len; ){
if(nums[i] != nums[j]){
res[idx ++ ] = nums[i];;
i ++ ;
j ++ ;
}
else{
i += 2;
j += 2;
}
}
if(j == len)
res[idx] = nums[i];
return res;
}
};
位运算
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int sum = 0;
for(int x : nums)
sum ^= x;
//此时sum == a ^ b;
int k = 0;
while(!(sum >> k & 1))//找到a和b的二进制表示第一个不相同的位
k ++ ;
int first = 0;
for(int x : nums){
if(x >> k & 1)//a和b的二进制表示在第k位时有所不同
//因为二进制的每一位只有两种可能:0或1,则可以用这
//个判定方法将a和b区分开。将a和所有第k位 == 1的成对
//的数字划分在一起,进行异或操作,最终成对的数字互相
//抵消,first == a;
first ^= x;
}
return {first, sum ^ first};
}
};