posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

          問題:
          給定n個(gè)32位無符號整數(shù),求出其中異或結(jié)果最大的兩個(gè)整數(shù)。

          例如
          給定1, 2, 3, 4, 0xFFFFFFFE
          1 XOR 0xFFFFFFFE的結(jié)果最大

          這題網(wǎng)上討論還不少,O(n logn)的方法很容易想,按二進(jìn)制值從高到低劃分就行了。
          這里有一個(gè)思路很清晰的O(n)的做法,用了字典樹
          http://discuss.joelonsoftware.com/default.asp?interview.11.614716

          首先建立一棵深度為32的二叉樹,結(jié)點(diǎn)值為0/1,每個(gè)整數(shù)對應(yīng)其中的一個(gè)葉子結(jié)點(diǎn),這樣一共有n個(gè)葉子。

          接下來,對于任一個(gè)整數(shù)x,先取反,m = ~x
          在二叉樹中找到和x異或后值最大的數(shù)(根據(jù)二進(jìn)制值的各位從樹根往下跑就行了,不過給出的代碼有點(diǎn)問題)
          找這個(gè)值在O(1)內(nèi)就能完成,然后求出最大的

          O(n)


          評論

          # re: 求n個(gè)32位無符號整數(shù)中異或后值最大的兩個(gè)數(shù)  回復(fù)  更多評論   

          2008-04-12 10:51 by 豆抓搜索
          學(xué)習(xí)..http://www.douzhua.com

          # re: 求n個(gè)32位無符號整數(shù)中異或后值最大的兩個(gè)數(shù)  回復(fù)  更多評論   

          2008-05-04 10:42 by ZelluX
          發(fā)現(xiàn)這個(gè)復(fù)雜度其實(shí)有問題,因?yàn)?2位無符號整數(shù)最多也就2^32次個(gè),樹的深度自然是個(gè)常數(shù)級別的,囧

          # re: 求n個(gè)32位無符號整數(shù)中異或后值最大的兩個(gè)數(shù)[未登錄]  回復(fù)  更多評論   

          2008-10-28 14:09 by dave
          ZelluX,請你重新解釋下O(n logn)和Trie的解法,或者提供相關(guān)鏈接。給出的鏈接已經(jīng)失效。非常感謝。

          # re: 求n個(gè)32位無符號整數(shù)中異或后值最大的兩個(gè)數(shù)[未登錄]  回復(fù)  更多評論   

          2008-10-28 20:09 by dave
          已經(jīng)明白Trie的解法,請博主說說O(n logn)的方法吧。

          # re: 求n個(gè)32位無符號整數(shù)中異或后值最大的兩個(gè)數(shù)  回復(fù)  更多評論   

          2008-12-05 17:00 by wzcsoft
          字典樹的方法實(shí)際上是O(n*k) k=32

          實(shí)際上不一定比O(nlgn)好,lgn往往小于32
          主站蜘蛛池模板: 屏东县| 宁安市| 长垣县| 宝丰县| 盐山县| 黔西| 仲巴县| 金秀| 静安区| 元谋县| 塔河县| 成都市| 仲巴县| 策勒县| 平谷区| 黑龙江省| 东宁县| 孟州市| 潜山县| 福建省| 绥中县| 庄河市| 津南区| 邯郸市| 五寨县| 泸西县| 乡宁县| 陆良县| 青州市| 望奎县| 略阳县| 祁东县| 灵寿县| 贵州省| 襄樊市| 独山县| 鄯善县| 高唐县| 贺兰县| 阿克苏市| 建湖县|