PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Missing Numbers

看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間10年前 (2014/11/10 22:16)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《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://www.ptt.cc/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://www.ptt.cc/bbs/Prob_Solve/M.1415628974.A.DDA.html