Posted on 2008-04-10 00:33
ZelluX 閱讀(4665)
評論(5) 編輯 收藏 所屬分類:
Algorithm
問題：
給定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)