LeetCode 421. Maximum XOR of Two Numbers in an Array--Python解法

LeetCode 421. Maximum XOR of Two Numbers in an Array–C++,Python解法

LeetCode题解专栏：LeetCode题解
我做的所有的LeetCode的题目都放在这个专栏里，大部分题目C++和Python的解法都有。

题目地址：Maximum XOR of Two Numbers in an Array - LeetCode

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

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.

这道题目意思很简单，就是找出异或结果最大的树，但最容易想到的解法就是穷举法。如果不穷举，很难想到其他方法可以把时间复杂度降到O(N)。

看了参考答案后，发现可以从最高位开始判断，一位一位的做，时间复杂度降到O(32N)。

Python解法如下：

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        # length of max number in a binary representation
        L = len(bin(max(nums))) - 2
        max_xor = 0
        for i in range(L)[::-1]:
            # go to the next bit by the left shift
            max_xor <<= 1
            # set 1 in the smallest bit
            curr_xor = max_xor | 1
            # compute all existing prefixes 
            # of length (L - i) in binary representation
            prefixes = {num >> i for num in nums}
            # Update max_xor, if two of these prefixes could result in curr_xor.
            # Check if p1^p2 == curr_xor, i.e. p1 == curr_xor^p2
            max_xor |= any(curr_xor^p in prefixes for p in prefixes)
                    
        return max_xor

另外一种解法是使用前缀树，但是使用了前缀树后时间复杂度虽然降低了，但实际运行实际变长了，这里就不写了。