※ 引述《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 解法呢？ : : -- :

※ 发信站: 批踢踢实业坊(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 : 推 dreamoon: k=2时，如何"很容易"的用xor的技巧找出答案? 11/10 03:51 令 x = 1 ~ n 所有数字的 xor，p 和 q 为两个不在 A 中的数字。 把 x 跟 A 中所有的数字作 xor，可以得到 y = p xor q。 因为 p != q，所以 y 至少有一个 bit 为 1，假设是第 m 个 bit。 在不失一般性的情况下，假设 a 的第 m 个 bit 为 1。 我们可以把 [1..n] 中的数字分成两群， Pm 包含所有 [1..n] 中第 m 个 bit 为 1 的所有数字，Qm 包含其他数字。 令 APm 为在 A 中的数字，其第 m 个 bit 为 1 的集合，这问题就变成 在 APm 中找出一个不在 Pm 中的数字了，可以使用 xor 技巧解决。 因为 m 只有 O(lg n) 种选择，可以先穷举所有可能的 Pm 和 Qm ， 然後 one-pass 就可以解决 k = 2 的特例。 当 k = 3 的时候，我也想到了一个方法，但是有点复杂。 令 p, q, r 为三个不在 A 中的数字，同样的我们可以计算出 y = p xor q xor r。 因为 p, q, r 是相异，所以 p, q, r, y 也必为相异。 令 f(a, b) = 2^j, j 是最小的 index of bit 使得 a 和 b 在 第 j 位不等， 如果 j 不存在 (a == b)，则f(a, b) = 0。 范例： 如果 a = 5 = 101, b = 3 = 011，则 f(a, b) = 010。 首先计算出 x = f(i, y) 的 xor 值，1 <= i <= n。 然後拿 x 跟 A 中所有元素 A[i] 的 f(A[i], y) 作 xor, 1 <= i <= n - 1。 结果为 z = f(p, y) xor f(q, y) xor f(r, y) 因为 f(a, y) 代表着是 a 和 y 中一个相异的 bit， z = f(p, y) xor f(q, y) xor f(r, y) 只有两种可能 如果 f(p, y), f(q, y), f(r, y) 皆相异，则 z 有 3 个 bit 为 1。 如果 f(p, y), f(q, y), f(r, y) 中有两个相同，则 z 有 1 个 bit 为 1。 如果 f(p, y), f(q, y), f(r, y) 皆相同，不可能发生，因为 y = p xor q xor r。 所以 z 至少有一个 bit 为 1，令其为第 m 位， 代表着 p, q, r 在 第 m 位不完全相同。 如果 y 的第 m 位是 1，p xor q xor r 在第 m 位为 1，又 p, q, r 在第 m 位不完全相同，代表其中有一个数字第 m 位为 1，其余两个数字 第 m 位为 0。 如果 y 的第 m 位是 0，类似的分析可以推导出其中有一个数字第 m 位为 0，其余 两个数字第 m 位为 1。 所以只要利用第 m 位的资讯，可以把 [1..n] 的数字分成两部分 B 和 C 其中 A 在 B 中缺一个数字， A 在 C 中缺两个数字，就可以分开解决。 要把这技巧推展到 k > 3，需要找出某一位 m，使得不存在 A 中的数字 可以被第 m 位分成两半，然後递回搜寻，但是好像挺复杂的.. --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 50.133.134.181 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1415628974.A.DDA.html