421. 数组中两个数的最大异或值

Difficulty
Medium
Tags
前缀树
URL
https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/
Star
给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
进阶：你可以在 O(n) 的时间解决这个问题吗？
示例 1：
输出：28
解释：最大运算结果是 5 XOR 25 = 28.
示例 2：
输入：nums = [0]
输出：0
示例 3：
输入：nums = [2,4]
输出：6
示例 4：
输入：nums = [8,10,2]
输出：10
示例 5：
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127
提示：
  • 1 <= nums.length <= 2 * 104
  • 0 <= nums[i] <= 231 - 1

法 1 字典树

思路
要达到 o(N)的时间复杂度，那么就需要将每一个数值 同时 与别的所有数字比较，当然可以搞一个长度为 32 的数组，然后从高位开始挨个遍历（为什么要从高位呢？因为高位权重大，得到的数字大！）
但是这样空间复杂度太高了，所以想到了树的形式。即前缀树！
题解
class TrieNode:
    def __init__(self):
        self.child = {}
    
class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for idx in range(31, -1, -1):
            bit = (num >> idx) & 1

            if bit not in node.child:
                node.child[bit] = TrieNode()
            node = node.child[bit]
    
    def xor(self, num):
        res = 0
        node = self.root
        for idx in range(31, -1, -1):
            bit = num >> idx & 1
            # 优先走不一样的！ 此时记得更新结果
            if 1-bit in node.child:
                # 将当前 值加上，或者直接 将 idx 位置为 1: res = res | (1 << idx)
                res += 1 << idx 
                res = res | (1 << idx)
                node = node.child[1-bit]
            else:
                node = node.child[bit]

        return res

      
class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        T = Trie()
        for num in nums:
            T.insert(num)

        max_xor = 0
        for num in nums:
            max_xor = max(max_xor, T.xor(num))

        return max_xor