- 前言
今天做的题中第二道题目是一道很好的题目，我的解法时间复杂度很差，可以根据类似自动机的思路改善复杂度。
- 136 Single Number
输入：vector<int>
输出：int
要求：nums中有一个数字出现了一次，其余数字出现了两次，返回这个数字。
思路：将所有的数字按位对齐，因为对于相同的两个数字相同位置的数字一定时相同的，且0^0==1^1==0，0^a==a，故可以使用将所有数字进行xor运算的方式求得这个数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
return accumulate(nums.begin(),nums.end(),0,bit_xor<int>());
}
};
- 137 Single Number II
输入输出和上边的相同。
要求：nums中有一个数字出现了一次，其余数字出现了三次，返回出现一次的数字
思路：按位数1的个数然后返回个数%3的结果
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for(int i = 0;i < 32;++ i){
int sum = 0;
for(int j = 0;j < nums.size();++ j){
sum += (nums[j] >> i) & 1;
}
ret |= (sum % 3) << i;
}
return ret;
}
};
- 260 Single Number III
输入和输出和上题相同。
要求：有两个数字出现了一次，其余出现了两次，返回这两个出现了一次的数字。
思路：假设nums中两个出现了一次的数字分别是a和b。首先得到diff = a^b，然后找区分a和b的方法（diff &= (~diff + 1))后就可以使用题目一中的方法来求a和b了。
class Solution
{
public:
vector<int> singleNumber(vector<int>& nums)
{
int diff = accumulate(nums.begin(),nums.end(),0,bit_xor<int>());
diff &= (~diff + 1);
vector<int> ret = {0,0};
for(auto a : nums){
if(diff & a) ret[0] ^= a;
else ret[1] ^= a;
}
return ret;
}
};
