Posted on 2008-04-10 00:33
ZelluX 阅读(4640)
评论(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)