# Single Number II ### Source - lintcode: [(83) Single Number II](http://www.lintcode.com/en/problem/single-number-ii/) ~~~ Given 3*n + 1 numbers, every numbers occurs triple times except one, find it. Example Given [1,1,2,3,3,3,2,2,4,1] return 4 Challenge One-pass, constant exstra space ~~~ ### 題解 - 逐位處理 上題 Single Number 用到了二進制中異或的運算特性，這題給出的元素數目為`3*n + 1`，因此我們很自然地想到如果有種運算能滿足「三三運算」為0該有多好！對于三個相同的數來說，其相加的和必然是3的倍數，僅僅使用這一個特性還不足以將單數找出來，我們再來挖掘隱含的信息。以3為例，若使用不進位加法，三個3相加的結果為： ~~~ 0011 0011 0011 ---- 0033 ~~~ 注意到其中的奧義了么？三個相同的數相加，不僅其和能被3整除，其二進制位上的每一位也能被3整除！因此我們只需要一個和`int`類型相同大小的數組記錄每一位累加的結果即可。時間復雜度約為 O((3n+1)?sizeof(int)?8)O((3n+1)\cdot sizeof(int) \cdot 8)O((3n+1)?sizeof(int)?8) ### C++ bit by bit ~~~ class Solution { public: /** * @param A : An integer array * @return : An integer */ int singleNumberII(vector<int> &A) { if (A.empty()) { return 0; } int result = 0, bit_i_sum = 0; for (int i = 0; i != 8 * sizeof(int); ++i) { bit_i_sum = 0; for (int j = 0; j != A.size(); ++j) { // get the *i*th bit of A bit_i_sum += ((A[j] >> i) & 1); } // set the *i*th bit of result result |= ((bit_i_sum % 3) << i); } return result; } }; ~~~ #### 源碼解析 1. 異常處理 1. 循環處理返回結果`result`的`int`類型的每一位，要么自增1，要么保持原值。注意`i`最大可取 8?sizeof(int)?18 \cdot sizeof(int) - 18?sizeof(int)?1, 字節數=>位數的轉換 1. 對第`i`位處理完的結果模3后更新`result`的第`i`位，由于`result`初始化為0，故使用或操作即可完成 ### Reference [Single Number II - Leetcode Discuss](https://leetcode.com/discuss/857/constant-space-solution?show=2542) 中拋出了這么一道擴展題： ~~~ Given an array of integers, every element appears k times except for one. Find that single one which appears l times. ~~~ @ranmocy 給出了如下經典解： We need a array `x[i]` with size `k` for saving the bits appears `i` times. For every input number a, generate the new counter by `x[j] = (x[j-1] & a) | (x[j] & ~a)`. Except `x[0] = (x[k] & a) | (x[0] & ~a)`. In the equation, the first part indicates the the carries from previous one. The second part indicates the bits not carried to next one. Then the algorithms run in `O(kn)` and the extra space `O(k)`. ### Java ~~~ public class Solution { public int singleNumber(int[] A, int k, int l) { if (A == null) return 0; int t; int[] x = new int[k]; x[0] = ~0; for (int i = 0; i < A.length; i++) { t = x[k-1]; for (int j = k-1; j > 0; j--) { x[j] = (x[j-1] & A[i]) | (x[j] & ~A[i]); } x[0] = (t & A[i]) | (x[0] & ~A[i]); } return x[l]; } } ~~~