Posted on 2008-04-10 00:33
ZelluX 閱讀(4657)
評論(5) 編輯 收藏 所屬分類:
Algorithm
問題：
給定n個32位無符號整數(shù)，求出其中異或結(jié)果最大的兩個整數(shù)。
例如
給定1, 2, 3, 4, 0xFFFFFFFE
1 XOR 0xFFFFFFFE的結(jié)果最大
這題網(wǎng)上討論還不少，O(n logn)的方法很容易想，按二進制值從高到低劃分就行了。
這里有一個思路很清晰的O(n)的做法，用了字典樹
http://discuss.joelonsoftware.com/default.asp?interview.11.614716
首先建立一棵深度為32的二叉樹，結(jié)點值為0/1，每個整數(shù)對應(yīng)其中的一個葉子結(jié)點，這樣一共有n個葉子。
接下來，對于任一個整數(shù)x，先取反，m = ~x
在二叉樹中找到和x異或后值最大的數(shù)（根據(jù)二進制值的各位從樹根往下跑就行了，不過給出的代碼有點問題）
找這個值在O(1)內(nèi)就能完成，然后求出最大的
O(n)