## 一.題目描述  ## 二.解題思路 這道題與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 出現一次、兩次、三次的分布情況，最后只需返回第一個變量就行了。這種方法我本人并沒有實現，日后再繼續研究。