Posted on 2008-04-10 00:33
ZelluX 阅读(1159)
评论(2) 编辑 收藏 所属分类:
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)