給定一長度為 n - k 的整數序列 A ，每個元素之範圍皆為 1 到 n 。
設計一個使用o(n)位元的演算法找出 k 個不在 A 中的整數 x，1 <= x <= n。
這問題的一般性解法在這裡 http://ppt.cc/Pwlk
此解法基於多項式分解，時間複雜度為多項式，而且是 one-pass。
但是當 k = 1 或是 2 的時候，可以很容易的用 xor 的技巧找出答案。
我的問題是，當 k > 2 的時候，有沒有辦法利用 xor 或是其他技巧，
構造出一個比較簡單的 multi-pass 解法呢？

k=2時，如何"很容易"的用xor的技巧找出答案?http://codepad.org/LRPxss39寫了一個空間複雜度O(k)的O(log n)-pass的方法也是多項式時間不知道符不符合你的需求@@?http://codepad.org/JE2jYW80

我有點不太懂程式碼 但是used array的space似乎很大??喔 我了解了 used 只是拿來 check 不是拿來計算但是 mask 好像可以很大.. 這樣 xr 和 num 空間是多少？

最多都是O(K)這方法某種程度和你下篇的方法很像就是一剛開始先把所有在A裡第一個bit是0或是1兩類若其中一類的個數恰少一個，我們就可以用該類的所有數的xor值來得知少的是哪個若該類少了至少兩個數例如說，第一個bit是0的那類少了至少兩個數我們就在下一次pass時把它變成前兩個bit是00和10兩類然後一直做下去用同樣的方法到最後就可以把所有少的數找出來只是這個方法要pass log n次過程中我們可以確定同一類裡分出來的兩類裡一定至少少了兩個數,所以在每個iteration中分類的類別總數一定<=K

了解了 我也想不出不用constant pass的方法了..如果先窮舉所有可能的 k bits 來分類 或許可以one pass..

想請教一下那個多項式解法，有滿足空間o(n)的條件嗎？我感覺矩陣二維陣列就已經是O(n * (n-k)) 了.. @@

什麼矩陣？

你只要枚舉1~n代進去看哪些數使得f(x)=0就行了

好像是這樣沒錯 但是要讓空間複雜度變成o(n)似乎是要在Zp之下運算才行 此時f(x) = 0 不代表 x 是解？我想了一下 應該沒有問題.. 只是這樣k不大的時候比較慢