题目描述：

LeetCode 421. Maximum XOR of Two Numbers in an Array

Given a list of numbers, a[0], a[1], a[2], … , a[N-1], where 0 <= a[i] < 2^32. Find the maximum result of a[i] XOR a[j].

Could you do this in O(n) runtime?

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

Output: 28

题目大意：

给定一列数字，a[0], a[1], a[2], … , a[N-1]，其中0 <= a[i] < 2^32。计算a[i] XOR a[j]的最大值。

你可以给出O(n)时间复杂度的解法吗？

解题思路：

解法I 分治法（Divide and Conquer）+ 位运算（Bit Manipulation）

求数组中两两数字的异或运算的最大值，朴素的解法是O(n ^ 2)，不满足题目要求。

异或运算（XOR）的实质是“同零异一”。

题目描述中a[i]的范围[0, 2^32)，至多有32位，因此可以通过位运算处理。

递归函数定义为：solve(nums0, nums1, mask)。

令mask从最高位（1<<31）向最低位（1）逐步右移，将数组nums按照如下规则分成两部分：

nums中，与mask按位与结果为0的所有数字，记为nums0

nums中，与mask按位与结果为1的所有数字，记为nums1

如果nums0与nums1其一为空，说明nums中所有数字在该二进制位同0或同1，其异或结果一定为0

如果nums0与nums1均不为空，说明nums中的数字在该位的异或值为1，令mask右移一位，再将nums0与nums1进一步划分成四部分：

nums0中，与mask按位与结果为0的所有数字，记为nums00

nums0中，与mask按位与结果为1的所有数字，记为nums01

nums1中，与mask按位与结果为0的所有数字，记为nums10

nums1中，与mask按位与结果为1的所有数字，记为nums11

分支1：如果nums00与nums11同时存在，递归求解solve(nums00, nums11, mask)的结果

分支2：如果nums01与nums10同时存在，递归求解solve(nums01, nums10, mask)的结果

从上述两个分支中求最大值ans

若ans为0，说明上述两分支均不存在，nums中mask对应二进制位的所有数字同0或者同1，此时计算分支3

分支3：递归计算solve(nums0, nums1, mask) - mask

最后将结果+mask * 2，并返回

Python代码：

class Solution(object):
    def findMaximumXOR(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def solve(nums0, nums1, mask):
            if mask <= 1: return mask

            mask /= 2
            nums01 = [n for n in nums0 if n & mask]
            nums00 = [n for n in nums0 if not n & mask]
            nums11 = [n for n in nums1 if n & mask]
            nums10 = [n for n in nums1 if not n & mask]

            ans = 0
            if nums10 and nums01:
                ans = max(ans, solve(nums10, nums01, mask))
            if nums00 and nums11:
                ans = max(ans, solve(nums00, nums11, mask))
            if not ans:
                ans = solve(nums0, nums1, mask) - mask
            return ans + mask * 2
        mask = 1 << 31
        while mask:
            nums0 = [n for n in nums if not n & mask]
            nums1 = [n for n in nums if n & mask]
            if nums0 and nums1: break
            mask >>= 1
        return solve(nums0, nums1, mask)

解法II Set数据结构 + 位运算

参阅LeetCode Discuss：https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap

Python代码：

class Solution(object):
    def findMaximumXOR(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = mask = 0
        for x in range(31, -1, -1):
            mask += 1 << x
            prefixSet = set([n & mask for n in nums])
            tmp = ans | 1 << x
            for prefix in prefixSet:
                if tmp ^ prefix in prefixSet:
                    ans = tmp
                    break
        return ans

解法III 字典树（Trie） + 位运算

参阅LeetCode Discuss：https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie

本文链接：http://bookshadow.com/weblog/2016/10/15/leetcode-maximum-xor-of-two-numbers-in-an-array/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码