Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

求n个32位无符号整数中异或后值最大的两个数

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


评论

# re: 求n个32位无符号整数中异或后值最大的两个数  回复  更多评论   

2008-04-12 10:51 by 豆抓搜索
学习..http://www.douzhua.com

# re: 求n个32位无符号整数中异或后值最大的两个数  回复  更多评论   

2008-05-04 10:42 by ZelluX
发现这个复杂度其实有问题,因为32位无符号整数最多也就2^32次个,树的深度自然是个常数级别的,囧

# re: 求n个32位无符号整数中异或后值最大的两个数[未登录]  回复  更多评论   

2008-10-28 14:09 by dave
ZelluX,请你重新解释下O(n logn)和Trie的解法,或者提供相关链接。给出的链接已经失效。非常感谢。

# re: 求n个32位无符号整数中异或后值最大的两个数[未登录]  回复  更多评论   

2008-10-28 20:09 by dave
已经明白Trie的解法,请博主说说O(n logn)的方法吧。

# re: 求n个32位无符号整数中异或后值最大的两个数  回复  更多评论   

2008-12-05 17:00 by wzcsoft
字典树的方法实际上是O(n*k) k=32

实际上不一定比O(nlgn)好,lgn往往小于32

只有注册用户登录后才能发表评论。


网站导航: