在 103 個數中有 50 個數出現了兩次、3 個數出現了一次，如何找出出現了一次的 3 個數？

01-21

acm題目，要求不可以新建一個num[53]數組來存放53個數出現的次數，空間複雜度為O(1)

。。。題目的評論下題主表示空間複雜度是要求額外O(1)，數組本身還是可以讀和寫的。。。於是顯然暴力n^2把n個數分別check一下出現了幾遍是可行的，所以我們現在可以考慮能把時間複雜度做到什麼程度了。。。

我們可以考慮從中位數入手，把數按&<中位數和&>=中位數分為兩邊，然後兩邊的數的個數必然是一奇一偶。我們把偶數個那邊求下xor和，若和為0，則說明3個數都在奇數那邊，於是可以把範圍縮小到一半（奇數那邊）；若不為0，則奇數那邊有1個，偶數那邊有2個，我們對奇數那邊求個xor和就知道奇數那邊那個是多少了，於是我們現在只用考慮偶數這邊的2個了。

於是繼續按中位數分為兩邊，兩邊個數的奇偶性是相同的。如果兩邊都是奇數個，那麼兩邊各求個xor和就知道分別是哪2個；如果都是偶數個，那麼求一下其中一邊的xor和，如果不為0則2個都在這邊，不為0則都在另一邊，然後範圍就又縮小到一半（不為0的那邊）了。

求中位數的話，分治成5組的那種穩定線性的演算法我不是太熟，但似乎因為遞歸是logn層的所以空間複雜度應該是O(logn)。。。但是random一個數分邊的那種期望複雜度為O(n)的演算法應該是可以通過維護當前區間的2個端點寫成非遞歸的，空間複雜度為O(1)，並且實際上可以直接按random的數分邊來做以上的演算法而不用求完中位數再分。然後上面演算法中的2個「範圍縮小」本質是把一個大的問題遞歸縮小到一個小的問題，但同樣可以通過維護當前區間端點做到非遞歸空間複雜度為O(1)的。這個演算法總的時間複雜度期望為O(n)，因為隨機所以最差情況出現的概率大約可以忽略不計了。。。

首先，空間必須得O(n)。

將所有數異或得到xors，所有數和xors異或的lowbit異或得到flag，滿足lowbit(num[i] ^ xors) == flag的數異或起來即可得到三個數中的一個a。

令xors^=a並把a也加入數組，再把所有滿足num[i] lowbit(xors) != 0的數異或得到一個數b，不滿足的異或起來得到c，則a,b,c就是所求的三個數。

時間複雜度:O(n)

空間複雜度:O(n)

參考:面試題: 找出數組中三個只出現一次的數

互聯網面試題：一個數組中找出三個出現奇數次的數字中的一個

神奇的異或運算

先吐槽：

1. 輸入數組居然可以寫，這是哪門子的 O(1) 空間複雜度呀！

輸入數組只能讀不能寫

2. 都說是 103 個數了，還哪來的 big-O notation 呀！

假設輸入可以任意長，其中 3 個數出現一次，其它數出現兩次

輸入：

設 $X$ 是這些數所在的集合，常見的範圍估計是 -2,147,483,648 to 2,147,483,647

設 $x_1,ldots,x_n$ 是輸入數組

演算法：

從一個 $X o {0,1}$ 的 2-universal hashing family 中隨機選取 $f$ ， $f$ 的作用就是 $X$ 大致隨機的分成兩組。有一半概率，三個單次出現的數中，有且只有一個落在 $f^{-1}(0)$ 中
計算 $igoplus_{substack{iin{1,ldots,n}\f(x_i)=0}} x_i$ ，有一半概率這就是一個單次出現的數，由 O(n) 時間檢查一下
重複 1.2. 直到所有單次出現的數都被找到。