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