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

k=2时，如何"很容易"的用xor的技巧找出答案?http://codepad.org/LRPxss39写了一个空间复杂度O(k)的O(log n)-pass的方法也是多项式时间不知道符不符合你的需求@@?http://codepad.org/JE2jYW80

我有点不太懂程式码 但是used array的space似乎很大??喔 我了解了 used 只是拿来 check 不是拿来计算但是 mask 好像可以很大.. 这样 xr 和 num 空间是多少？

最多都是O(K)这方法某种程度和你下篇的方法很像就是一刚开始先把所有在A里第一个bit是0或是1两类若其中一类的个数恰少一个，我们就可以用该类的所有数的xor值来得知少的是哪个若该类少了至少两个数例如说，第一个bit是0的那类少了至少两个数我们就在下一次pass时把它变成前两个bit是00和10两类然后一直做下去用同样的方法到最后就可以把所有少的数找出来只是这个方法要pass log n次过程中我们可以确定同一类里分出来的两类里一定至少少了两个数,所以在每个iteration中分类的类别总数一定<=K

了解了 我也想不出不用constant pass的方法了..如果先穷举所有可能的 k bits 来分类 或许可以one pass..

想请教一下那个多项式解法，有满足空间o(n)的条件吗？我感觉矩阵二维阵列就已经是O(n * (n-k)) 了.. @@

什么矩阵？

你只要枚举1~n代进去看哪些数使得f(x)=0就行了

好像是这样没错 但是要让空间复杂度变成o(n)似乎是要在Zp之下运算才行 此时f(x) = 0 不代表 x 是解？我想了一下 应该没有问题.. 只是这样k不大的时候比较慢