Find number which only appears once - II

在一個數組裡找出只出現過一次的數，其他數都出現 3次

這題就不能用 XOR 做了，因為會讓所有的數都 XOR 在一起

可以想的是在電腦上一個整數是怎麼表示的，是用 32-bit 表示

那我們可以把數拆成二進制，開一個紀錄數組，然後在相對應的位置加一

比如說 4 就會是 00000000 00000000 00000000 0000 0100

如果數組是 [4, 4, 4, 8] 可以表示成 0000000 00000000 00000000 0000 1300

把重覆的數用到的 1 都乘以 3，用這樣來表示這個數有三個

</p>

例如 [7, 7, 7, 1] => 00000000 00000000 00000000 0000 0334

最後把每個數字都 % 3，那麼就可以得到一個相當於二進制的數組，在算出是多少即可

public int findSingleInteger(int[] A) {
    int bits[] = new int[32];
    for (int i = 0; i < 32; i++) {
        bits[i] = 0;
    }

    for (int index = 0; index < A.length; index++) {
        for (int j = 0; j < 32; j++) {
            bits[j] += ((A[index] >> j) & 1);  //record every digit
        }
    }

    int result = 0;
    for (int i = 0; i < 32; i++) {
        result += (bits[i] % 3) << i;
    }
    return result;
}

時間複雜度為 O(32*n) => O(n)

</p>

觀察：

找偶數次的可以用 XOR

找奇數次的就要 Hashmap 或是這個方法