PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] Missing Numbers

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