1. 题目来源
- 分类：字典树
- Leetcode421:数组中两个数的最大异或值
2. 题目描述
给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。你能在O(n)的时间解决这个问题吗？
示例:
输入: [3, 10, 5, 25, 2, 8]
输出: 28
解释: 最大的结果是 5 ^ 25 = 28.
3. 解题思路
根据Trie Tree(字典树/前缀树/单词查找树)对Trie基本结构的描述，编写构建结点，以及构建trie树，以及trie树的基本操作方法。
本题的解题思路：Trie树 + 位运算
【Trie树】Trie树建立的思路，整数在存储时需要32bit，因此可以把整数看作为含有32字符的字符串，其中每个字符为0或1，则可以使用二叉树构建前缀树。从高位到低位进行构建，其中左结点为1，右结点为0.
【位运算找最大异或值】如何找到最大值异或，两个数异或得到一个尽可能大的数，则第一个1出现的位数越高则数越大，所以可以从最高位开始，找和它相反的数，如果存在这这个数异或即得到最大异或值，若不存在则，则继续相下找，直到找到相异的位。
对于25 (0000 0000 0000 0000 0000 0000 0001 1001) 而言，使得异或结果最大的数x为0000 0000 0000 0000 0000 0000 000* ****
从根节点开始搜索，node = root，直至到第5位，当前node为第6位右分支。
25第5位为1，则x的第5位为0，结果为最大，选择右分支，node = node.zero；
25第4位为1，则x的第4位为0，结果为最大，选择右分支，node = node.zero；
25第3位为0，则x的第3位为1，结果为最大，选择左分支，node = node.one；
25第2位为0，则x的第2位为1，结果为最大，当前node.one为空，所以选择node.zero, node = node.zero；
25第1位为1，则x的第1位为0，结果为最大，当前node.zero为空，所以选择node.one, node = node.one；最终找到x为5(00101)。
对于数组中每一个数进行上述操作，更新最大异或值。
建立Trie树的时间复杂度是O(32n)，这里的32即Trie树的键值最大长度；Trie树的高度为32，因此查找每个数的最大异或值得时间复杂度是O(32n)，合起来是O(64n)也即时间复杂度为O(n)
4. 编程实现
Python
class TrieNode:
def __init__(self):
self.one = None
self.zero = None
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
#构建前缀树
root = TrieNode()
for num in nums:
node = root
#从最高位开始到最低位顺序进行构建
for i in range(31, -1, -1):
temp = num & (1 << i)
if temp:
if not node.one:
node.one = TrieNode()
node = node.one
else:
if not node.zero:
node.zero = TrieNode()
node = node.zero
#求最大异或值
res = 0
for num in nums:
node = root
xor = 0
for i in range(31, -1, -1):
temp = num & (1 << i)
if node.zero and temp:
node = node.zero
#对于2进制最终转换为10进制的结果1/0 * 2^n + ...
xor += 1 << i
elif node.one and not temp:
node = node.one
xor += 1 << i
else:
node = node.one or node.zero
res = max(res, xor)
return res
参考学习：
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/130427/()-92
http://bookshadow.com/weblog/2016/10/15/leetcode-maximum-xor-of-two-numbers-in-an-array/
