leetcode筆記：Single Number II

一.題目描述

二.解題思路

這道題與Single Number（數組中其他數出現兩次，僅有一個出現一次的）有所不同，本題變為序列中有一個數出現一次，其他元素出現了三次，同樣要求時間復雜度為線性，空間復雜度為常數。事實上，該算法仍可以借助位運算來實現。

首先需要確定int類型數據的長度：intWidth = sizeof(int) * 8，可以用intWidth大小的變量來存儲數組中每個元素的各個二進制位上1 出現的次數，最後 在進行 模3 操作，如果為1，那說明這一位是要找元素二進制表示中為 1 的那一位。

一個例子<喎?/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPqO6PC9wPg0KPHA+0tTPwtPQ0rvX6dDywdCjrNC0s/bDv7j2yv21xLb+vfjWxtDOyr2jujwvcD4NCjxwcmUgY2xhc3M9"brush:java;"> 13：1 1 0 1 13：1 1 0 1 13：1 1 0 1 8： 1 0 0 0 9： 1 0 0 1 9： 1 0 0 1 9： 1 0 0 1

統計每一位二進制位上 1 出現的次數，由高位到低位依次為：7 3 0 6 ，最後對7 3 0 6 中各元素進行模3(%3)，得到：1 0 0 0 ，即為出現一次的數的二進制表示，返回該值即可。實際上對於該命題的擴展，即：若存在一序列，除了一個數只出現一次，其他數均出現k次的情況下，同樣可使用以上方法，對每一位二進制位上 1 出現的次數進行統計，最後進行模k(%k)即得到目標值。

// 時間復雜度O(n)，空間復雜度O(1)
class Solution 
{
public:
    int findSingleNumber(int A[], int n) 
    {
        const int intWidth = sizeof(int) * 8;
        int bitNum[intWidth] = { 0 };  // initialize
        int res = 0;
        for (int i = 0; i < intWidth; i++){
            for (int j = 0; j < n; j++){
                bitNum[i] += (A[j] >> i) & 1;
            }
            res |= (bitNum[i] % 3) << i;
        }
        return res;
    }
};