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:
Input: [2,2,3,2] Output: 3
Example 2:
Input: [0,1,0,1,0,1,99] Output: 99
数组中有出现3次的数，但是也有一个出现1次的数，现在要把这个只出现1次的数找出来。要求是线性时间复杂度和常数空间复杂度。 相比于LeetCode Single Number有难度。网上看到一个很不错的题解，分析得很详细。 初级解法是，把数组中每个数字的对应二进制位加起来，因为3个相同的数对应二进制位加起来之后模3一定等于0，比如5的二进制为101，三个101加起来就是303，每一位模3就是000。所以如果混入了一个只出现一次的数，这样取模之后，剩余位为1的就是我们要找的数的二进制形式。 这种解法需要一个32位的数组，用来统计所有数每一位出现1的次数之和，所以空间复杂度是O(32)=O(1)。时间复杂度的话，相当于O(32n)=O(n)，是线性的。完整代码如下：
class Solution {
public:
int singleNumber(vector<int>& nums)
{
int bit_len = sizeof(int) * 8;
vector<int> bit(bit_len, 0);
for (int i = 0; i < bit_len; ++i) {
for (int j = 0; j < nums.size(); ++j) {
bit[i] += (nums[j] & 1);
nums[j] >>= 1;
}
}
int ans = 0;
for (int i = 0; i < bit_len; ++i) {
int r = bit[i] % 3;
ans |= (r << i);
}
return ans;
}
};本代码提交AC，用时12MS。
高级解法是，使用三个int的每一位表示所有数每一位出现1次数之和的情况，one对应位为1表示这一位出现了1次1，two对应位为1表示这一位出现了2次1，three对应位为1表示这一位出现了3次1。但是one,two,three对应位不可能都同时为1。
通过分析对应位的关系（请看原博客），发现one,two,three可以快速通过位运算计算得到。完整代码如下：
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;
}
};本代码提交AC，用时15MS。
初级解法还是好理解一些，会不会是一个通用的解法呢，比如数组中出现1次和出现4次（甚至k次）的数混在一起，都可以通过模k求解呢？