作者FRAXIS (喔喔)
看板Prob_Solve
标题[问题] 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 解法呢？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 129.170.195.149
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1415549389.A.937.html
※ 编辑: FRAXIS (129.170.195.149), 11/10/2014 01:25:08
1F：推 dreamoon: k=2时，如何"很容易"的用xor的技巧找出答案? 11/10 03:51
3F：→ dreamoon: 写了一个空间复杂度O(k)的O(log n)-pass的方法 11/10 04:51
4F：→ dreamoon: 也是多项式时间 11/10 04:52
5F：→ dreamoon: 不知道符不符合你的需求@@? 11/10 04:53
7F：→ FRAXIS: 我有点不太懂程式码 但是used array的space似乎很大?? 11/10 21:03
8F：→ FRAXIS: 喔 我了解了 used 只是拿来 check 不是拿来计算 11/10 21:12
9F：→ FRAXIS: 但是 mask 好像可以很大.. 这样 xr 和 num 空间是多少？ 11/10 21:18
10F：→ dreamoon: 最多都是O(K) 11/11 08:50
11F：→ dreamoon: 这方法某种程度和你下篇的方法很像 11/11 08:50
12F：→ dreamoon: 就是一刚开始先把所有在A里第一个bit是0或是1两类 11/11 08:51
13F：→ dreamoon: 若其中一类的个数恰少一个，我们就可以用该类的所有数的 11/11 08:52
14F：→ dreamoon: xor值来得知少的是哪个 11/11 08:53
15F：→ dreamoon: 若该类少了至少两个数 11/11 08:54
16F：→ dreamoon: 例如说，第一个bit是0的那类少了至少两个数 11/11 08:54
17F：→ dreamoon: 我们就在下一次pass时把它变成前两个bit是00和10两类 11/11 08:55
18F：→ dreamoon: 然後一直做下去 11/11 08:55
19F：→ dreamoon: 用同样的方法到最後就可以把所有少的数找出来 11/11 08:56
20F：→ dreamoon: 只是这个方法要pass log n次 11/11 08:56
21F：→ dreamoon: 过程中我们可以确定同一类里分出来的两类里一定至少少了 11/11 08:57
22F：→ dreamoon: 两个数,所以在每个iteration中分类的类别总数一定<=K 11/11 08:58
23F：→ FRAXIS: 了解了 我也想不出不用constant pass的方法了.. 11/11 22:22
24F：→ FRAXIS: 如果先穷举所有可能的 k bits 来分类 或许可以one pass.. 11/11 22:27
25F：推 yoco315: 想请教一下那个多项式解法，有满足空间o(n)的条件吗？ 11/18 14:38
26F：→ yoco315: 我感觉矩阵二维阵列就已经是O(n * (n-k)) 了.. @@ 11/18 14:39
27F：→ FRAXIS: 什麽矩阵？ 11/18 21:38
28F：推 dreamoon: 你只要枚举1~n代进去看哪些数使得f(x)=0就行了 11/19 19:53
29F：→ FRAXIS: 好像是这样没错 但是要让空间复杂度变成o(n) 11/19 22:12
30F：→ FRAXIS: 似乎是要在Zp之下运算才行 此时f(x) = 0 不代表 x 是解？ 11/19 22:12
31F：→ FRAXIS: 我想了一下 应该没有问题.. 只是这样k不大的时候比较慢 11/20 05:07