137. Single Numver II

Given a **non-empty** array of integers, every element appears *three* times except for one, which appears exactly once. Find that single one.

**Note:**

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

**Example 1:**

1
2
Input: [2,2,3,2]
Output: 3
**Example 2:**
1
2
Input: [0,1,0,1,0,1,99]
Output: 99
思路:利用计算机按位存储数字的特性来做,除了一个单独的数字之外,数组中其他数字都出现了三次,那么还是要利用位操作来解此题。我们可以建立一个32位的数字,来统计每一位上1出现的个数,我们知道如果某一位上为1的话,那么如果该整数出现了三次,对3去余为0,我们把每个数的对应位都加起来对3取余,最终剩下来的那个数就是单独的数字。代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (int i = 0; i < 32; ++i) {
int sum = 0;
for (int j = 0; j < nums.size(); ++j) {
sum += (nums[j] >> i) & 1;
}
res |= (sum % 3) << i;
}
return res;
}
};
Runtime: 8ms, Ranking 61.74% 另外有解法2和3,如下:
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) {
two |= one & nums[i];
one ^= nums[i];
three = one & two;
one &= ~three;
two &= ~three;
}
return one;
}
};
解法3:
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int singleNumber(vector<int>& nums) {
int a = 0, b = 0;
for (int i = 0; i < nums.size(); ++i) {
b = (b ^ nums[i]) & ~a;
a = (a ^ nums[i]) & ~b;
}
return b;
}
};
网页链接:http://www.cnblogs.com/grandyang/p/4263927.html ​

开始尝试难度为m或H的题目,关键是弄懂: