題目描述（中等難度）

136 題 的升級版，這個題的話意思是，每個數(shù)字都出現(xiàn)了 3 次，只有一個數(shù)字出現(xiàn)了 1 次，找出這個數(shù)字。同樣要求時間復雜度為 O（n），空間復雜度為 O（1）。

大家可以先看一下 136 題 ，完全按 136 題 的每個解法去考慮一下。

解法一

先不考慮空間復雜度，用最常規(guī)的方法。

可以用一個 HashMap 對每個數(shù)字進行計數(shù)，然后返回數(shù)量為 1 的數(shù)字就可以了。

public int singleNumber(int[] nums) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(nums[i])) {
            map.put(nums[i], map.get(nums[i]) + 1);
        } else {
            map.put(nums[i], 1);
        }
    }
    for (Integer key : map.keySet()) { 
        if (map.get(key) == 1) {
            return key;
        }

    }
    return -1; // 這句不會執(zhí)行
}

時間復雜度：O（n）。

空間復雜度：O（n）。

解法二 數(shù)學推導

回想一下 136 題 中，每個數(shù)字都出現(xiàn)兩次，只有一個數(shù)字出現(xiàn) 1 次是怎么做的。

假設我們的數(shù)字是 a b a b c c d

怎么求出 d 呢？

只需要把出現(xiàn)過的數(shù)字加起來乘以 2 ，然后減去之前的數(shù)字和就可以了。

什么意思呢？

上邊的例子出現(xiàn)過的數(shù)字就是 a b c d ，加起來乘以二就是 2 * ( a + b + c + d)，之前的數(shù)字和就是 a + b + a + b + c + c + d 。

2 * ( a + b + c + d) - (a + b + a + b + c + c + d)，然后結(jié)果是不是就是 d 了。。。。。。

看完這個解法我只能說 tql。。。

找出現(xiàn)過什么數(shù)字，我們只需要一個 Set 去重就可以了。

這里的話每個數(shù)字出現(xiàn)了 3 次，所以我們可以加起來乘以 3 然后減去之前所有的數(shù)字和。這樣得到的差就是只出現(xiàn)過一次的那個數(shù)字的 2 倍。

public int singleNumber(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        set.add(nums[i]);
        sum += nums[i];
    }
    int sumMul = 0;
    for (int n : set) {
        sumMul += n;
    }
    sumMul = sumMul * 3;
    return (sumMul - sum) / 2;
}

然而并沒有通過

原因就是 int 是 32 位整數(shù)，計算機中是以補碼表示的，詳細的參考 趣談補碼 。
問題的根本就出現(xiàn)在，如果 2a = c ，那么對于 a 的取值有兩種情況。在沒有溢出的情況下，a = c/2 是沒有問題的。但如果 a 是很大的數(shù)，加起來溢出了，此時 a = c >>> 1。

舉個具體的例子，

如果給定的數(shù)組是 [1 1 1 Integer.MaxValue]。如果按上邊的解法最后得到的就是

(1 + Ingeger.MaxValue) * 3 - (1 + 1 + 1 + Integer.MaxValue) = 2 * Integer.MaxValue

由于產(chǎn)生了溢出

2 * Integer.MaxValue = -2，最后我們返回的結(jié)果就是 -2 / 2 = -1。

所以這個思路行不通了，因為無法知道是不是會溢出。

解法三 位操作

136 題通過異或解決了問題，這道題明顯不能用異或了，參考 這里 的一個解法。

我們把數(shù)字放眼到二進制形式

假如例子是 1 2 6 1 1 2 2 3 3 3, 3 個 1, 3 個 2, 3 個 3,1 個 6
1 0 0 1
2 0 1 0 
6 1 1 0 
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1  
3 0 1 1
3 0 1 1      
看最右邊的一列 1001100111 有 6 個 1
再往前看一列 0110011111 有 7 個 1
再往前看一列 0010000 有 1 個 1
我們只需要把是 3 的倍數(shù)的對應列寫 0，不是 3 的倍數(shù)的對應列寫 1    
也就是 1 1 0,也就是 6。

原因的話，其實很容易想明白。如果所有數(shù)字都出現(xiàn)了 3 次，那么每一列的 1 的個數(shù)就一定是 3 的倍數(shù)。之所以有的列不是 3 的倍數(shù)，就是因為只出現(xiàn)了 1 次的數(shù)貢獻出了 1。所以所有不是 3 的倍數(shù)的列寫 1，其他列寫 0 ，就找到了這個出現(xiàn) 1 次的數(shù)。

public int singleNumber(int[] nums) {
    int ans = 0;
    //考慮每一位
    for (int i = 0; i < 32; i++) {
        int count = 0;
        //考慮每一個數(shù)
        for (int j = 0; j < nums.length; j++) {
            //當前位是否是 1
            if ((nums[j] >>> i & 1) == 1) {
                count++;
            }
        }
        //1 的個數(shù)是否是 3 的倍數(shù)
        if (count % 3 != 0) {
            ans = ans | 1 << i;
        }
    }
    return ans;
}

時間復雜度：O（n）。

空間復雜度：O（1）。

解法四 通用方法

參考 這里。

解法三中，我們將數(shù)字轉(zhuǎn)為二進制，統(tǒng)計了每一位的 1 的個數(shù)。我們使用了一個 32位 的 int 來統(tǒng)計。事實上，我們只需要看它是不是 3 的倍數(shù)，所以我們只需要兩個 bit 位就夠了。初始化為 00，遇到第一個 1 變?yōu)?01，遇到第二個 1 變?yōu)?10，遇到第三個 1 變回 00 。接下來就需要考慮怎么做到。

本來想按自己理解的思路寫一遍，但 這里 寫的很好了，主要還是翻譯下吧。

將問題一般化

給一個數(shù)組，每個元素都出現(xiàn) k ( k > 1) 次，除了一個數(shù)字只出現(xiàn) p 次(p >= 1, p % k !=0)，找到出現(xiàn) p 次的那個數(shù)。

考慮其中的一個 bit

為了計數(shù) k 次，我們必須要 m 個比特，其中 ，也就是 m >= logk。

假設我們 m 個比特依次是 。

開始全部初始化為 0。00...00。

然后掃描所有數(shù)字的當前 bit 位，用 i 表示當前的 bit。

也就是解法三的例子中的某一列。

假如例子是 1 2 6 1 1 2 2 3 3 3, 3 個 1, 3 個 2, 3 個 3,1 個 6
1 0 0 1
2 0 1 0 
6 1 1 0 
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1  
3 0 1 1
3 0 1 1   

初始 狀態(tài) 00...00。

第一次遇到 1 , m 個比特依次是 00...01。

第二次遇到 1 , m 個比特依次是 00...10。

第三次遇到 1 , m 個比特依次是 00...11。

第四次遇到 1 , m 個比特依次是 00..100。

x1 的變化規(guī)律就是遇到 1 變成 1 ，再遇到 1 變回 0。遇到 0 的話就不變。

所以 x1 = x1 ^ i，可以用異或來求出 x1 。

那么 x2...xm 怎么辦呢？

x2 的話，當遇到 1 的時候，如果之前 x1 是 0，x2 就不變。如果之前 x1 是 1，對應于上邊的第二次遇到 1 和第四次遇到 1。 x2 從 0 變成 1 和 從 1 變成 0。

所以 x2 的變化規(guī)律就是遇到 1 同時 x1 是 1 就變成 1，再遇到 1 同時 x1 是 1 就變回 0。遇到 0 的話就不變。和 x1 的變化規(guī)律很像，所以同樣可以使用異或。

x2 = x2 ^ (i & x1)，多判斷了 x1 是不是 1。

x3，x4 ... xm 就是同理了，xm = xm ^ (xm-1 & ... & x1 & i) 。

再說直接點，上邊其實就是模擬了每次加 1 的時候，各個比特位的變化。所以高位 xm 只有當?shù)臀蝗繛?1 的時候才會得到進位 1 。

00 -> 01 -> 10 -> 11 -> 00

上邊有個問題，假設我們的 k = 3，那么我們應該在 10 之后就變成 00，而不是到 11。

所以我們需要一個 mask ，當沒有到達 k 的時候和 mask進行與操作是它本身，當?shù)竭_ k 的時候和 mask 相與就回到 00...000。

根據(jù)上邊的要求構造 mask，假設 k 寫成二進制以后是 km...k2k1。

mask = ~(y1 & y2 & ... & ym),

如果kj = 1，那么yj = xj

如果 kj = 0，yj = ~xj 。

舉兩個例子。

k = 3: 寫成二進制，k1 = 1, k2 = 1, mask = ~(x1 & x2);

k = 5: 寫成二進制，k1 = 1, k2 = 0, k3 = 1, mask = ~(x1 & ~x2 & x3);

很容易想明白，當 x1x2...xm 達到 k1k2...km 的時候因為我們要把 x1x2...xm 歸零。我們只需要用 0 和每一位進行與操作就回到了 0。

所以我們只需要把等于 0 的比特位取反，然后再和其他所有位相與就得到 1 ，然后再取反就是 0 了。

如果 x1x2...xm 沒有達到 k1k2...km ，那么求出來的結(jié)果一定是 1，這樣和原來的 bit 位進行與操作的話就保持了原來的數(shù)。

總之，最后我們的代碼就是下邊的框架。

for (int i : nums) {
    xm ^= (xm-1 & ... & x1 & i);
    xm-1 ^= (xm-2 & ... & x1 & i);
    .....
    x1 ^= i;
    
    mask = ~(y1 & y2 & ... & ym) where yj = xj if kj = 1, and yj = ~xj if kj = 0 (j = 1 to m).

    xm &= mask;
    ......
    x1 &= mask;
}

考慮全部 bit

假如例子是 1 2 6 1 1 2 2 3 3 3, 3 個 1, 3 個 2, 3 個 3,1 個 6
1 0 0 1
2 0 1 0 
6 1 1 0 
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1  
3 0 1 1
3 0 1 1   

之前是完成了一個 bit 位，也就是每一列的操作。因為我們給的數(shù)是 int 類型，所以有 32 位。所以我們需要對每一位都進行計數(shù)。有了上邊的分析，我們不需要再向解法三那樣依次考慮每一位，我們可以同時對 32 位進行計數(shù)。

對于 k 等于 3 ，也就是這道題。我們可以用兩個 int，x1 和 x2。x1 表示對于 32 位每一位計數(shù)的低位，x2 表示對于 32 位每一位計數(shù)的高位。通過之前的公式，我們利用位操作就可以同時完成計數(shù)了。

int x1 = 0, x2 = 0, mask = 0;

for (int i : nums) {
    x2 ^= x1 & i;
    x1 ^= i;
    mask = ~(x1 & x2);
    x2 &= mask;
    x1 &= mask;
}

返回什么

最后一個問題，我們需要返回什么？

解法三中，我們看 1 出現(xiàn)的個數(shù)是不是 3 的倍數(shù)，不是 3 的倍數(shù)就將對應位置 1。

這里的話一樣的道理，因為所有的數(shù)字都出現(xiàn)了 k 次，只有一個數(shù)字出現(xiàn)了 p 次。

因為 xm...x2x1 組合起來就是對于每一列 1 的計數(shù)。舉個例子

假如例子是 1 2 6 1 1 2 2 3 3 3, 3 個 1, 3 個 2, 3 個 3,1 個 6
1 0 0 1
2 0 1 0 
6 1 1 0 
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1  
3 0 1 1
3 0 1 1   
    
看最右邊的一列 1001100111 有 6 個 1, 也就是 110
再往前看一列 0110011111 有 7 個 1, 也就是 111
再往前看一列 0010000 有 1 個 1, 也就是 001
再對應到 x1, x2, x3 就是
x1 1 1 0
x2 0 1 1
x3 0 1 1

如果 p = 1，那么如果出現(xiàn)一次的數(shù)字的某一位是 1 ，一定會使得 x1 ，也就是計數(shù)的最低位置的對應位為 1，所以我們把 x1 返回即可。對于上邊的例子，就是 110 ，所以返回 6。

如果 p = 2，二進制就是 10，那么如果出現(xiàn) 2次的數(shù)字的某一位是 1 ，一定會使得 x2 的對應位變?yōu)?1，所以我們把 x2 返回即可。

如果 p = 3，二進制就是 11，那么如果出現(xiàn) 3次的數(shù)字的某一位是 1 ，一定會使得 x1 和x2的對應位都變?yōu)?code>1，所以我們把 x1 或者 x2 返回即可。

所以這道題的代碼就出來了

public int singleNumber(int[] nums) {
    int x1 = 0, x2 = 0, mask = 0;
    for (int i : nums) {
        x2 ^= x1 & i;
        x1 ^= i;
        mask = ~(x1 & x2);
        x2 &= mask;
        x1 &= mask;
    }
    return x1; 
}

至于為什么先對 x2 異或再對 x1 異或，就是因為 x2 的變化依賴于 x1 之前的狀態(tài)。顛倒過來明顯就不對了。

再擴展一下題目，對于 k = 5, p = 3 怎么做，也就是每個數(shù)字出現(xiàn)了5 次，只有一個數(shù)字出現(xiàn)了 3 次。

首先根據(jù) k = 5，所以我們至少需要 3 個比特位。因為 2 個比特位最多計數(shù)四次。

然后根據(jù) k 的二進制形式是 101，所以 mask = ~(x1 & ~x2 & x3)。

根據(jù) p 的二進制是 011，所以我們最后可以把 x1 返回。

public int singleNumber(int[] nums) {
    int x1 = 0, x2 = 0, x3  = 0, mask = 0;
    for (int i : nums) {
        x3 ^= x2 & x1 & i;
        x2 ^= x1 & i;
        x1 ^= i;
        mask = ~(x1 & ~x2 & x3);
        x3 &= mask;
        x2 &= mask;
        x1 &= mask;
    }
    return x1;  
}

而 136 題 中，k = 2, p = 1 ，其實也是這個類型。只不過因為 k = 2，而我們用一個比特位計數(shù)的時候，等于 2 的時候就自動歸零了，所以不需要 mask，相對來說就更簡單了。

public int singleNumber(int[] nums) {
    int x1 = 0;

    for (int i : nums) {
        x1 ^= i;
    }

    return x1;
}

這個解法真是太強了，完全回到二進制的操作，五體投地了，推薦再看一下英文的 原文 分析，太強了。

總

解法一利用 HashMap 計數(shù)很常規(guī)，解法二通過數(shù)學公式雖然沒有通過，但溢出的問題也就我們經(jīng)常需要考慮的。解法三把數(shù)字放眼到二進制，統(tǒng)計 1 的個數(shù)已經(jīng)很強了。解法四直接利用 bit 位來計數(shù)，真的是大開眼界了，神仙操作。

更多詳細通俗題解詳見 leetcode.wang 。