分享一道解法巧妙的演演算法題

最近碰到很多透過巧妙著運用位運算來巧妙解決複雜問題的演演算法，今天分享的這道題，或許能夠開拓你的一些演演算法思維。

題目描述

有一組存放 ID 的資料。並且 ID 取值為 0 – (N-1) 之間，其中只有一個 ID 出現的次數為 1，其他的 ID 出現的次數都等於 2，問如何找到這個次數為 1 的 ID ?

解法一：巧用陣列下標

不知道有多少人還記得我之前分享的巧用陣列下標的技巧：一些常用的演演算法技巧總結。

我的第一想法便是採用下標法來解決，把 ID 作為陣列 arr 的下標，在遍歷 ID 的過程中，用陣列記下每個 ID 出現的次數，即每次遍歷到 ID = n，則 arr[n]++。

之後我們在遍歷陣列 arr，找到 arr[n] = 1 的ID，該下標 n 便是我們要尋找的目的 ID。

這種方法的時間複雜度為 O(N)，空間複雜度為 O(N)。

解法二：巧用雜湊表

顯然時間複雜度是無法再降低的了，因為我們必須要遍歷所有的 ID，所以時間複雜度最少都得為 O(N)了，所以我們要想辦法降低空間複雜度。

大家想一個問題，假如我們檢測到某個 ID 已經出現了 2 次了，那麼這個 ID 的資料我們還需要儲存記錄嗎？大部分的 ID 都出現了 2 次，這一大部分的資料真的需要儲存嗎？

答是不用的，因為出現 2 次的 ID 不是我們所要找的。所以我們可以最佳化解法一，我們可以採用雜湊表來記錄 ID 出現的次數：利用雜湊表記下每個 ID 出現的次數，每次遇見一個 ID，就把這個 ID 放進 雜湊表，如果這個 ID 出現了次數已經為 2 了，我們就把這個 ID 從雜湊表中移除，最後雜湊表只會剩下一個我們要尋找的 ID。

這個方法最好的情況下空間複雜度可以降低到 O(1)，最壞的情況仍然了 O(N)。

解法三：巧用位運算

那究竟有沒辦法讓空間複雜度在最壞的情況下也是 O(1) 呢？

答是有的，按就是採用異或運算。異或運算有個特點：

異或運算特點：相同的兩個數異或之後，結果為 0，任何數與0異或運算，其結果不變並且，異或運算支援結合律。

所以，我們可以把所有的 ID 進行異或運算，由於那些出現兩次的 ID 透過異或運算之後，結果都為 0，而出現一次的 ID 與 0 異或之後不變，又因為異或支援結合律，所以，把所有 ID 進行異或之後，最後的結果便是我們要找的 ID。

這個方法的空間複雜度為 O(1)，巧妙利用了位運算，而且運算的效率是非常高效的。

問題拓展

假如有 2 個 ID 出現的次數為 1，其他 ID 出現的次數都為 2 呢？有該如何解決呢？是否還是可以用位運算呢？

為了方便這裡我們先假設 異或 的符號為 @，

答是必須的，假如這兩個出現一次的 ID 分別為 A, B，則所有 ID 異或後的結果為 A@B，這時我們遇到的問題是無法確定 A，B的值。

由於 A 和 B 是不一樣的值，所以 A@B 的結果不為 0，也就是說，這個異或值的二進制中某一位為1。顯然，A 和 B 中有且僅有一個數的相同位上也為 1。

這個時候，我們可以把所有 ID 分為兩類，一類在這個位上為 1，另一類為 0，那麼對於這兩類，一類會含有 A，另一類會含有 B。於是，我們可以分別計算這兩類 ID 的異或值，幾可得到 A 和 B 的值。

總結

大家做刷題的時候，不妨多加上一個想法：是否可以用的上位運算這種思路。有收穫？不妨來個好看讓更多人看到這篇文章！