LeetCode-Maximum XOR of Two Numbers in an Array

问题：

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.

Follow up: Could you do this in O(n) runtime?

Example 1:

Input:

 nums = [3,10,5,25,2,8]

Output:

 28

Explanation:

Constraints:

• 1 <= nums.length <= 2 * 10⁴
• 0 <= nums[i] <= 2³¹ - 1

解答：

1. 穷举

将所有情况进行穷举，时间复杂度O(n2) ，不过不符合题目要求

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        maxXor = 0
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                maxXor = max(maxXor, nums[i]^nums[j])
    return maxXor'''

1. Trie树

时间复杂度O(n), 不过需要提前构建trie树

class Trie:
    def __init__(self):
        self.children = [None]*2
        
class Solution:
    def __init__(self):
        self.root = Trie()
        
    def findMaximumXOR(self, nums: List[int]) -> int:
        for num in nums:
            self.insert(num)
        res = 0
        for num in nums:
            res = max(res, self.findMaxXOR(num))
        return res
    
    def findMaxXOR(self, num):
        res = 0
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if node.children[bit^1] is None:
                node = node.children[bit]
            else:
                node = node.children[bit^1]
                res |= 1<<i
        return res
    
    def insert(self,num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if node.children[bit] is None:
                node.children[bit] = Trie()
            node = node.children[bit]

参考及引用

图片来源 twitter Ice Angel @addyiceangel