[LeetCode]Maximum XOR of Two Numbers in an Array

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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