Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
421. Maximum XOR of Two Numbers in an Array.go
421. Maximum XOR of Two Numbers in an Array_test.go
README.md

README.md

421. Maximum XOR of Two Numbers in an Array

题目:

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

题目大意

给定一个非空数组,数组中元素为 a0, a1, a2, … , an-1,其中 0 ≤ ai < 2^31 。找到 ai 和 aj 最大的异或 (XOR) 运算结果,其中0 ≤ i,  j < n 。你能在O(n)的时间解决这个问题吗?

解题思路

  • 这一题最先考虑到的解法就是暴力解法,2 层循环,依次计算两两数之间的异或值,动态维护最大的值,遍历完成以后输出最大值即可。提交代码会发现超时。

  • 改进一点的做法就是一层循环。试想,求的最终结果是一个 32 位的二进制数,如果想要这个数最大,那么高位都填满 1 就是最大。所以从高位开始尝试,先把数组里面所有的高位都放进 map 中,然后利用异或的交换律,a ^ b = ca ^ c = b,当我们知道 a 和 c 的时候,可以通过交换律求出 b。a 就是我们遍历的每个数,c 是我们想要尝试的高位最大值,例如,111…000,从高位逐渐往低位填 1 。如果我们求的 b 也在 map 中,那么就代表 c 是可以求出来的。如果 c 比当前的 max 值要大,就更新。按照这样的方式遍历往 32 位,每次也遍历完整个数组中的每个数,最终 max 里面就是需要求的最大值。

  • 还有更好的做法是利用 Trie 这个数据结构。构建一棵深度为 33 的二叉树。root 节点左孩子为 1,右孩子为 0 代表着所有数字的最高位,其次根据次高位继续往下。如果某一个节点左右子树都不为空,那么得到最终答案的两个数字肯定分别出自于左右子树且此位为 1;如果任意一个为空,那么最终答案该位为 0,依次迭代得到最终结果。具体做法见:Java O(n) solution using Trie - LeetCode Discuss

  • 最后还有更“完美的做法”,利用 leetcode 网站判题的特性,我们可以测出比较弱的数据,绕过这组弱数据可以直接 AC。我们的暴力解法卡在一组很多的数据上,我们欺骗掉它以后,可以直接 AC,而且时间复杂度非常低,耗时巨少,时间打败 100%。

You can’t perform that action at this time.