给定一长度为 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 解法呢?