leetcode筆記：Single Number II

leetcode筆記：Single Number II

一.題目描述

二.解題思路

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

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

一個例子：

以下有一組序列，寫出每個數的二進制形式：

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;
    }
};

四.總結

閱讀了網上其他博文，發現事實上有更為高效的方法，其基本思路是利用三個變量分別保存各個二進制位上 1 出現一次、兩次、三次的分布情況，最後只需返回第一個變量就行了。這種方法我本人並沒有實現，日後再繼續研究。