题目链接：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?

这道题的要求是给定一个数组，出了一个元素出现1次以外其余每个元素都出现3次，找到只出现1次的元素。

  1. Hash

算是Single Number的升级版，不过采用Hash的思路完全相同：

用Hash表记录每个出现的元素，最后输出只出现1次的即可。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution
{
public:
    int singleNumber(int A[], int n)
    {
        unordered_map<int, int> m;
        for(int i = 0 ; i < n; ++ i)
            ++ m[A[i]];
        for(auto it = m.begin(); it != m.end(); ++ it)
            if(it -> second == 1)
                return it -> first;
        return 0;
    }
};

  1. 位操作

不过不能和Single Number同样简单地采用异或操作，这里需要采用3个变量进行标识：

  • ones表示第i位出现1次；
  • twos表示第i位出现2次；
  • threes表示第i位出现3次。

接下来，当第i为出现3次后，把ones和twos中对应的第i位清0。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution
{
public:
    int singleNumber(int A[], int n)
    {
        int ones = 0, twos = 0, threes = 0;
        for(int i = 0; i < n; ++ i)
        {
            twos |= ones & A[i];
            ones ^= A[i];
            threes = ones & twos;
            ones &= ~threes;
            twos &= ~threes;
        }
        
        return ones;
    }
};

详见这里。