[心得] 尋找missing number
之前準備面試問題的筆記,跟大家分享。
一個常見的問題是,給定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
推
06/24 23:27, , 1F
06/24 23:27, 1F
※ 編輯: FRAXIS 來自: 140.119.162.51 (06/25 08:22)
→
06/25 08:22, , 2F
06/25 08:22, 2F
推
06/25 08:53, , 3F
06/25 08:53, 3F