HashTable

最简单的是使用Hash表,暂且按下不表。

位操作

对于Single Number,可以很简单的使用异或操作完成:

1
2
3
4
5
6
7
8
9
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for (int i = 0; i < nums.size(); i++)
result ^= nums[i];
return result;
}
};

对于第二个题,Single Number II,先可以使用一个长度为32的int数组来记录每一位1出现的次数,也就可以了:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
int bit[32] = {0};
for (int i = 0; i < 32; i++) {
for (int j = 0; j < nums.size(); j++)
bit[i] += (nums[j] >> i) & 1;
result |= (bit[i] % 3) << i;
}
return result;
}
};

这个是比较通用的解法,可以拓展;

对于第二个题其实还可以使用一种比较tricky的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int singleNumber(vector<int>& nums) {
int one = 0, two = 0, three = 0;
for (int i = 0; i < nums.size(); i++) {
three = two & nums[i];
two |= one & nums[i];
one ^= nums[i];
two &= ~three;
one &= ~three;
}
return one;
}
};