推 karcher:宇集為有序集合且子集為有序集合，直接做match比較快 06/24 23:27
※ 編輯: FRAXIS 來自: 140.119.162.51 (06/25 08:22)
→ FRAXIS:我把題目再增加了一些說明.. 06/25 08:22
推 willhunting:相當變態的題目 06/25 08:53
之前準備面試問題的筆記，跟大家分享。
一個常見的問題是，給定n-1個相異整數，範圍是1~n，找出數字k, 1 <= k <= n，
且k不在那n-1個整數之中，輸入給的時候沒有排序，同時輸入陣列是唯讀的，
另外n非常的大，大到不可能開一個長度為n的陣列。
（類似程式之美書中的1.5題）
線性時間且只使用常數空間的方法我只知道有兩種（有人知道其他方法嘛？）：
1. 先把1 ~ n xor起來，然後再跟這n-1個數字做xor。
2. 把1 ~ n加起來，然後扣掉n-1個數字，但是可能會overflow。
同樣的道理也可以處理給定n+1個數字，範圍是1~n，只有數字k出現兩次，
其他數字都只出現一次，找出k的問題。
如果現在的情形是n-2個相異整數，要找出哪兩個數字a, b沒出現的話。
（或是n+2個整數，只有兩個數字出現兩次，要找出哪兩個出現過）
我知道有三種方法
1. 先把1~n加起來然後扣掉n-2個整數，這樣就可以得到a + b。
再把1~n乘起來，然後除以n-2個整數，這樣就可以得到a * b。
配合上1 <= a, b <= n, 解聯立方程式。
2. 先把1~n加起來然後扣掉n-2個整數，這樣就可以得到a
把1^2 ~ n^2加起來，然後扣掉n-2個整數各自的平方，
這樣就可以得到a^2 + b^2。
配合上1 <= a, b <= n, 解聯立方程式。
（基本上這意義跟方法1差不多）
3. 先把1~n xor起來，然後xor這n-2個整數，就可以得到一個數字r。
如果r的第i個bit為1，代表a和b在這個bit是不同的。
假設a在這個bit為1，然後把1~n中這個bit為1的先xor起來，再跟
n-2個數字中該bit為1的做xor，就可以得到a了。
有了a自然就可以得到b了。
如果給定n-k個相異整數，要找出哪k個數字沒出現過的話，
用上面的方法2去延伸，應該是可以解的出來的。而且xor法也可以
只是會比較麻煩，下面就會介紹。
先把問題延伸成一個更一般化的問題，給定一群整數，範圍沒有限制。
除了幾個數字之外，其他的數字都出現偶數次。
原本的問題，可以轉化成這個一般化問題而得到解答。假設要從n-1個
範圍是1~n的數字找出不存在的數字k，只要把1~n的數字和原本輸入的
n-1個數字當成輸入餵給一般化的問題即可。（滿足除了一個數字之外
其他數字都出現兩次）
現在要介紹怎麼解這一般化問題。
假設除了一個數字k之外，其他都出現過偶數次，很顯然的只要把所有
數字xor起來就是答案。
如果除了兩個數字a, b之外，其他都出現過偶數次，要找出a和b的
話。先把所有數字xor起來，找出a和b那個bit不同，再把原本輸入
集合按照該bit是0還是1來切割，就可以找出a和b了。
接著，如果除了三個數字a, b, c之外，其他都出現偶數次，要找出
a, b, c的話，首先要把所有數字都xor起來，結果為s = a^b^c，而
且s != a, s != b, s != c（不然就代表a,b,c中有數字相同）。
接下來，把原本輸入中的每一個數字x拿出來跟s做比較，找出x和s
第一個不同的位置（用x^s & ~((x^s)-1)達成）。然後把這群位置
xor起來，假設結果是r。
r的bit pattern有兩種，因為除了三個數字之外的其他數字都是成
對出現，所以只要考慮那三個數字即可。如果那三個數字與s的第一
個不同位置都相異，就會使得r的3個bit為1。如果那三個數字之中
有兩個數字與s的第一個不同位置一樣，那麼就會使得r的1個bit為1。
如果三個數字與s的第一個不同位置都相同，這種情況不會發生。
可用反證法證明，假設該位置s為0，那麼a, b, c在該位置都會為1
，但是s是由a^b^c得來的，s不可能為0，矛盾。（s該位置為1的情況是對稱的）
所以這樣就成功的找出某一個bit，可以把這三個數字作區隔了。
如果s的第i個bit為0，代表a^b^c的第i個bit為0，只有兩種可能，就
是0, 0, 0或是0, 1, 1（不考慮排列），但是從r的條件我們知道至少
有一個數字的第i個bit不是0，所以唯一的可能就是後者。
如果s的第i個bit為1，代表a^b^c的第i個bit為1，只有兩種可能，就
是1, 1, 1或是1, 0, 0（不考慮排列），但是從r的條件我們知道至少
有一個數字的第i個bit不是1，所以唯一的可能就是後者。
所以只要第i個bit為0或是1，把原始輸入做區分，就可以得到三個
數字的其中一個。算出一個之後，問題就簡化成尋找兩個只出現奇
數次的數字的問題了。
如果要把問題再延伸到尋找四個只出現奇數次的數字，已經超出我
能力範圍了，有人知道怎麼用xor法去找4個以上只出現奇數次的數字嘛？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.51