排序 + 位运算
排序是很简单的,位运算有两个思路:中规中矩的开长度为32的数组把原数组的每个数字的每一位都记录下来,最后再分别 % 3;状态机的思路非常难想。
排序
class Solution {
public:
int singleNumber(vector<int>& nums) {
quickSort(nums, 0, nums.size() - 1);
int len = nums.size();
int i = 0, j = 1, ans = -1;
while(j < len){
if(nums[i] != nums[j]){
ans = nums[i];
break;
}
else{
i += 3;
j += 3;
}
}
if(i == len - 1)
ans = nums[len - 1];
return ans;
}
void quickSort(vector<int>& nums, int l, int r){
if(l == r)
return ;
int i = l - 1, j = r + 1, pivot = nums[l + (r - l) / 2];
while(i < j){
while(nums[ ++ i] < pivot);
while(nums[ -- j] > pivot);
if(i < j)
swap(nums[i], nums[j]);
}
quickSort(nums, l, j);
quickSort(nums, j + 1, r);
}
};
位运算(朴实无华)
class Solution {
public:
int singleNumber(vector<int>& nums) {
int len = nums.size();
vector<int> res(32, 0);
for(int x : nums){
for(int j = 0; j < 32; j ++ ){
res[j] += x >> j & 1;
}
}
long long sum = 0, power = 1;
for(int i = 0; i < 32; i ++ ){
res[i] %= 3;
sum += res[i] * power;
power *= 2;
}
return sum;
}
位运算(状态机)
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ones = 0, twos = 0;
for(int x : nums){
ones = (ones ^ x) & ~twos;
twos = (twos ^ x) & ~ones;
}
return ones;
}
};