leetcode-single-number-ii

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/single-number-ii/

　　数组中只有一个数出现一次，其它数都出现三次。要求时间复杂度O(n)，空间复杂度为O(1)

题目分析

　　思路参考了这里：http://www.acmerblog.com/leetcode-single-number-ii-5394.html

　　第一种比较直观的思路是：因为每个数字都有32位，把数组中所有的元素对应位相加，32位中的每一位都可以得到一个和，把这个和模3得到的结果（注意模3的结果只能是0和1，不可能是2）就是答案在该位的值。但这种方法需要频繁地移位操作，虽然时间和空间能满足题目要求。

　　第二种思路代码更为精简和巧妙，https://discuss.leetcode.com/topic/2031/challenge-me-thx/25 这里利用真值表+状态机解释的，本质上就是用两个bit代表00，01，10这三个状态，然后在这三个状态之间基于某种规则转移。贴一下思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
I think many coder confused how to generate the code.
This is my analysis, use Truth table to generate code:
Consider every bit in a number, if this bit appear 3 times then set it to zero.
so here is 3 state of one bit, we can use two bit to indicate it.
we use 00 -> 01 -> 10 -> 00...
00: bit 1 appear 0 time.
01: bit 1 appear 1 time.
10: bit 1 appear 2 times.
so every bit 1 appear 3 times, the state will go to 00
but for the single number, every bit 1 in it, its status is 01
we can use two integer to represent the status, named first, second
Now problem is how to generate the code to change 'first' and 'second'
I use truth table to generate the code, like this:
count every '1' bit, 3 times to zero
so we need 3 status, 2 bit is enough
state: 00 -> 01 -> 10 -> 00....
so we can draw a truth table of first bit
A: first bit
B: second bit
C: input bit
A B C NA NB
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 1 0
1 0 1 0 0
1 1 0 not define
1 1 1 not define

　　第三种思路就是用三个变量ones,twos,threes直接统在那些位上出现了几次1，参考了这里：https://github.com/soulmachine/leetcode。可以理解成用二进制模拟了三进制加法，思路比较好理解。

代码

　　第一种思路

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

　　第二种思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int singleNumber(vector<int>& A) {
        int first = 0, second = 0;
        for (int i = 0; i < n; ++i) {
            int lastFirst = first;
            first = ~second & (first ^ A[i]);
            second = (~second&lastFirst&A[i])|(second&~lastFirst&~A[i]);
        }
    }
};

　　第三种思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0;
        int twos = 0;
        int threes = 0;
        for (int i : nums) {
            twos |= (ones & i);
            ones ^= i;
            threes = ~(ones & twos);
            ones &= threes;
            twos &= threes;
        }
        return ones;
    }
}