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