Re: [問題] Missing Numbers

作者: FRAXIS (喔喔)   2014-11-10 22:16:11
※ 引述《FRAXIS (喔喔)》之銘言:
: 標題: [問題] 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 解法呢?
:
:

Links booklink

Contact Us: admin [ a t ] ucptt.com