LeetCode Single Number II

class Solution {
public:
    int singleNumber(int A[], int n) {
        sort(A, A+n);
        int last = A[0];
        int time = 1;
        for (int i=1; i<n; i++) {
            if (last != A[i]) {
                if(time == 3) {
                    time = 1;
                    last = A[i];
                    continue;
                }
                return last;
            }
            time++;
        }
        if (time != 3) return last;
    }
};

一时想不出线性的方法

第二轮：

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 class Solution {
 2 public:
 3     int singleNumber(int A[], int n) {
 4         int bitcount[32] = {0};
 5         for (int i=0; i<n; i++) {
 6             int cur = A[i];
 7             for (int i=0; i<32 & cur != 0; i++) {
 8                 bitcount[i] += cur & 0x1;
 9                 cur>>=1;
10             }
11         }
12         int num = 0;
13         for (int i=32-1; i>=0; i--) {
14             num<<=1;
15             num|=bitcount[i] % 3 != 0;
16         }
17         return num;
18     }
19 };

还是用这个方法吧。