作者FRAXIS (喔喔)
看板Prob_Solve
標題[問題] Missing Numbers
時間Mon Nov 10 00:09:46 2014
給定一長度為 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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1415549389.A.937.html
※ 編輯: FRAXIS (129.170.195.149), 11/10/2014 01:25:08
1F：推 dreamoon: k=2時，如何"很容易"的用xor的技巧找出答案? 11/10 03:51
3F：→ dreamoon: 寫了一個空間複雜度O(k)的O(log n)-pass的方法 11/10 04:51
4F：→ dreamoon: 也是多項式時間 11/10 04:52
5F：→ dreamoon: 不知道符不符合你的需求@@? 11/10 04:53
7F：→ FRAXIS: 我有點不太懂程式碼 但是used array的space似乎很大?? 11/10 21:03
8F：→ FRAXIS: 喔 我了解了 used 只是拿來 check 不是拿來計算 11/10 21:12
9F：→ FRAXIS: 但是 mask 好像可以很大.. 這樣 xr 和 num 空間是多少？ 11/10 21:18
10F：→ dreamoon: 最多都是O(K) 11/11 08:50
11F：→ dreamoon: 這方法某種程度和你下篇的方法很像 11/11 08:50
12F：→ dreamoon: 就是一剛開始先把所有在A裡第一個bit是0或是1兩類 11/11 08:51
13F：→ dreamoon: 若其中一類的個數恰少一個，我們就可以用該類的所有數的 11/11 08:52
14F：→ dreamoon: xor值來得知少的是哪個 11/11 08:53
15F：→ dreamoon: 若該類少了至少兩個數 11/11 08:54
16F：→ dreamoon: 例如說，第一個bit是0的那類少了至少兩個數 11/11 08:54
17F：→ dreamoon: 我們就在下一次pass時把它變成前兩個bit是00和10兩類 11/11 08:55
18F：→ dreamoon: 然後一直做下去 11/11 08:55
19F：→ dreamoon: 用同樣的方法到最後就可以把所有少的數找出來 11/11 08:56
20F：→ dreamoon: 只是這個方法要pass log n次 11/11 08:56
21F：→ dreamoon: 過程中我們可以確定同一類裡分出來的兩類裡一定至少少了 11/11 08:57
22F：→ dreamoon: 兩個數,所以在每個iteration中分類的類別總數一定<=K 11/11 08:58
23F：→ FRAXIS: 了解了 我也想不出不用constant pass的方法了.. 11/11 22:22
24F：→ FRAXIS: 如果先窮舉所有可能的 k bits 來分類 或許可以one pass.. 11/11 22:27
25F：推 yoco315: 想請教一下那個多項式解法，有滿足空間o(n)的條件嗎？ 11/18 14:38
26F：→ yoco315: 我感覺矩陣二維陣列就已經是O(n * (n-k)) 了.. @@ 11/18 14:39
27F：→ FRAXIS: 什麼矩陣？ 11/18 21:38
28F：推 dreamoon: 你只要枚舉1~n代進去看哪些數使得f(x)=0就行了 11/19 19:53
29F：→ FRAXIS: 好像是這樣沒錯 但是要讓空間複雜度變成o(n) 11/19 22:12
30F：→ FRAXIS: 似乎是要在Zp之下運算才行 此時f(x) = 0 不代表 x 是解？ 11/19 22:12
31F：→ FRAXIS: 我想了一下 應該沒有問題.. 只是這樣k不大的時候比較慢 11/20 05:07