421. 数组中两个数的最大异或值
给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
进阶：你可以在 O(n) 的时间解决这个问题吗？
示例 1：
输入：nums = [3,10,5,25,2,8]
输出：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 * 1040 <= nums[i] <= 231 - 1
位运算 中等 每日一题
https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/
题解
解题思路
这道题目还是蛮有意思的，用到前缀树的思想来将复杂度降低到 O(N)。
我们分两步来解决这个问题：
- 构建二进制前缀树
具体来说就是利用数的二进制表示，从高位到低位构建一棵树（因为只有
0和1两个值，所以是一棵二叉树），每个从根节点到叶子节点的路径都表示一个数。（构建的树看下图） - 搜索前缀树
然后遍历数组中的数字，将每一个二进制位，在对应的层中找到一个与或的最大值，也就是：如果是
1，找0的那条路径，如果是0，找1的那条路径。 这样搜索下来的路径就是这个数字和整个数组与或的最大值，看下图
具体步骤是：
对于2， 二进制从高到低是 0，0，1，0
- 第一步：二进制位是
0，我们到第四层去选择，有1，我们选择1这个节点，与或计算结果是1 - 第二步：二进制位是
0，在第三层，上一步选择的节点没有为1的子节点，所以我们只能选择0，与或计算结果是0 - 第三步：二进制位是
1，在第二层，上一步选择的节点的子节点下有0的节点，我们选择0，与或计算结果是1 - 第四部：二进制位是
0，在第一层，上一步选择的节点的子节点下只有一个0，所以选择0，与或计算结果是0
所以我们与或的结果是1010， 十进制表示是10.
分析：
其实每个数字还是都要和其他数字做个异或，不过利用了前缀树和贪心思想，每一步都挑一个最大的值，把其他路径都剪枝掉了。
复杂度分析
- 构建前缀树，遍历一个数字，是
O(N), 对于每个数字，遍历每一个二进制位，由于数字最大是32位，所以是常数，总的复杂度为O(N)，树的最大层次也是32层(这个还可以优化，取当前数组中所有数的最长二进制表示即可，肯定小于等于32位) - 搜索前缀树，遍历每一个数字，是
O(N), 对于数字的每个二进制位，我们要往下搜索树，不过树的层次是一个常数，所以总的复杂度还是O(N)
总体复杂度为 O(N)
代码
class TrieNode:
def __init__(self):
self.children = defaultdict(TrieNode)
class Trie:
def __init__(self, nums):
self.root = TrieNode()
for n in nums:
self.insert(n)
def insert(self, n): # 从右向左每一位插入Trie
cur = self.root
for i in range(31, -1, -1):
cur = cur.children[(n>>i) & 1]
def searchMax(self, n):
res, cur = 0, self.root
for i in range(31, -1, -1): # 从右向左找最多xor=1的儿子
bit = (n>>i) & 1
if bit ^ 1 in cur.children: # 找到就向儿子走
cur = cur.children[bit ^ 1]
res += (1<<i)
else: # 没找到就向bit走，因为有可能之后会找到xor=1的儿子
cur = cur.children[bit]
return res
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
t = Trie(nums)
return max([t.searchMax(n) for n in nums])