2014
11-19

LeetCode-Single Number II[数组]

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

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

// LeetCode, Single Number II
// 方法1，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
int singleNumber(int A[], int n) {
const int W = sizeof(int) * 8; // 一个整数的bit数，即整数字长
int count[W];  // count[i]表示在在i位出现的1的次数
fill_n(&count[0], W, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < W; j++) {
count[j] += (A[i] >> j) & 1;
count[j] %= 3;
}
}
int result = 0;
for (int i = 0; i < W; i++) {
result += (count[i] << i);
}
return result;
}
};

// LeetCode, Single Number II
// 方法2，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
int singleNumber(int A[], int n) {
int one = 0, two = 0, three = 0;
for (int i = 0; i < n; ++i) {
two |= (one & A[i]);
one ^= A[i];
three = ~(one & two);
one &= three;
two &= three;
}

return one;
}
};

Single Number

1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确

2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

4. 有一点问题。。后面动态规划的程序中
int dp[n+1][W+1];
会报错 提示表达式必须含有常量值。该怎么修改呢。。