[問題] Missing Numbers

[FRAXIS (喔喔)]

給定一長度為 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 解法呢？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1415549389.A.937.html
※ 編輯: FRAXIS (129.170.195.149), 11/10/2014 01:25:08
推 dreamoon: k=2時，如何"很容易"的用xor的技巧找出答案?
→ dreamoon: http://codepad.org/LRPxss39
→ dreamoon: 寫了一個空間複雜度O(k)的O(log n)-pass的方法
→ dreamoon: 也是多項式時間
→ dreamoon: 不知道符不符合你的需求@@?
→ dreamoon: http://codepad.org/JE2jYW80
→ FRAXIS: 我有點不太懂程式碼  但是used array的space似乎很大??
→ FRAXIS: 喔 我了解了 used 只是拿來 check 不是拿來計算
→ FRAXIS: 但是 mask 好像可以很大.. 這樣 xr 和 num 空間是多少？
→ dreamoon: 最多都是O(K)
→ dreamoon: 這方法某種程度和你下篇的方法很像
→ dreamoon: 就是一剛開始先把所有在A裡第一個bit是0或是1兩類
→ dreamoon: 若其中一類的個數恰少一個，我們就可以用該類的所有數的
→ dreamoon: xor值來得知少的是哪個
→ dreamoon: 若該類少了至少兩個數
→ dreamoon: 例如說，第一個bit是0的那類少了至少兩個數
→ dreamoon: 我們就在下一次pass時把它變成前兩個bit是00和10兩類
→ dreamoon: 然後一直做下去
→ dreamoon: 用同樣的方法到最後就可以把所有少的數找出來
→ dreamoon: 只是這個方法要pass log n次
→ dreamoon: 過程中我們可以確定同一類裡分出來的兩類裡一定至少少了
→ dreamoon: 兩個數,所以在每個iteration中分類的類別總數一定<=K
→ FRAXIS: 了解了  我也想不出不用constant pass的方法了..
→ FRAXIS: 如果先窮舉所有可能的 k bits 來分類 或許可以one pass..
推 yoco315: 想請教一下那個多項式解法，有滿足空間o(n)的條件嗎？
→ yoco315: 我感覺矩陣二維陣列就已經是O(n * (n-k)) 了.. @@
→ FRAXIS: 什麼矩陣？
推 dreamoon: 你只要枚舉1~n代進去看哪些數使得f(x)=0就行了
→ FRAXIS: 好像是這樣沒錯  但是要讓空間複雜度變成o(n)
→ FRAXIS: 似乎是要在Zp之下運算才行 此時f(x) = 0 不代表 x 是解？
→ FRAXIS: 我想了一下 應該沒有問題.. 只是這樣k不大的時候比較慢