看板 [ Prob_Solve ]
討論串[問題] Missing Numbers
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] Missing Numbers
推噓3(3推 0噓 28→)留言31則，0人參與, 最新作者FRAXIS (喔喔)時間10年前 (2014/11/10 00:09), 10年前編輯資訊
1
0
2
內容預覽:
給定一長度為 n - k 的整數序列 A ，每個元素之範圍皆為 1 到 n 。. 設計一個使用o(n)位元的演算法找出 k 個不在 A 中的整數 x，1 <= x <= n。. 這問題的一般性解法在這裡 http://ppt.cc/Pwlk. 此解法基於多項式分解，時間複雜度為多項式，而且是 one
(還有130個字)
#2
Re: [問題] Missing Numbers
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者FRAXIS (喔喔)時間10年前 (2014/11/10 22:16), 編輯資訊
0
0
3
內容預覽:
令 x = 1 ~ n 所有數字的 xor，p 和 q 為兩個不在 A 中的數字。. 把 x 跟 A 中所有的數字作 xor，可以得到 y = p xor q。. 因為 p != q，所以 y 至少有一個 bit 為 1，假設是第 m 個 bit。. 在不失一般性的情況下，假設 a 的第 m 個 b
(還有1216個字)
首頁
上一頁
1
下一頁
尾頁