2021.5.16
421.数组中两个数的最大异或值
https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/
给你一个整数数组 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 * 10^40 <= nums[i] <= 2^31 - 1
 学到的知识点：字典树的实际应用
 真就异或周了（
 这题最容易想到的方法当然是二重循环遍历了，但是O($n^2$)的时间复杂度没法通过所有的用例。
 虽然不看答案我也想不到字典树能这么用，但还是记录一下思考过程：
 首先题目要求的是取两个数得到最大异或值，异或运算是按位异或，所以能得到的最理想状况，就是先找到数组中二进制最高位的位置最大的那个数，然后这个数有一些位可能是0，那么就在数组中找一个能够把这些0补上的一个比较小的数。
 当然，根据上面的分析会容易想当然地认为，我们要找到最大的那个数，然后再找一个比较小的数，就能得到答案，但是看示例4：[8,10,2]，即[1000,1010,0010]，如果我们先拿出10这个数，那么能得到的最大异或值是10⊕2=8，但是实际上8⊕2=10，比8要大，所以这个二进制最高位的位置最大的那个数可能并不是数组中最大的那个数，那么要如何找到这个比较大的数就是个麻烦的问题了。
 看了官方题解之后发现，这道题的重点在于，我们需要从高位向低位判断最终答案的每一二进制位能否取到1。
 结合题目中给的提示，将时间复杂度限制在O(n)以内，联想到力扣第一题使用哈希表的做法，可以想到，应该是要使用某种数据结构，将查找过的数据存起来，然后在低于O(n)的时间内进行一次查找。
 官方题解的方法一，使用哈希表的做法比较难以理解，但是方法二使用字典树的做法还是很好懂的。力扣第一题能够将时间复杂度压缩到O(n)的关键就在于，对于数组中每个数，在哈希表中查找合适的答案的时间复杂度为O(1)，而在字典树中查找一个元素的时间复杂度为O(C)，其中C为字符串的最大长度。此处由于所有数据都是32位有符号整型数字，所以C为31。此外，由于此处将数据视作二进制字符串存入字典树，而二进制数每一位只有0和1两种取值，所以整个字典树实际上是一颗二叉树，并且所有叶子结点都在同一层。
 代码实现：（C#）
class Trie{
public Trie left=null;//左子树作为选择1的路径
public Trie right=null;//0
}
public class Solution {
int maxBit=30;
Trie root=new Trie();
public int FindMaximumXOR(int[] nums) {
if(nums.Length==1)return 0;
int ans=0;
Add(nums[0]);
for(int i=1;i<nums.Length;i++){
ans=Math.Max(ans,Check(nums[i]));
Add(nums[i]);
}
return ans;
}
///向字典树中添加一条数据
public void Add(int num){
Trie temp=root;
for(int i=maxBit;i>=0;i--){
if(((num>>i)&1)==1){
if(temp.left==null)
temp.left=new Trie();
temp=temp.left;
}
else{
if(temp.right==null)
temp.right=new Trie();
temp=temp.right;
}
}
}
///在字典树中查找最合适的一个数据，返回得到的异或结果
public int Check(int num){
int x=0;
Trie temp=root;
for(int i=maxBit;i>=0;i--){
if(((num>>i)&1)==1){//进行查找的原数字这一位为1，则优先找字典树中这一位为0的数字
if(temp.right!=null){
temp=temp.right;
x=x*2+1;
}
else{
temp=temp.left;
x=x*2;
}
}
else{
if(temp.left!=null){
temp=temp.left;
x=x*2+1;
}
else{
temp=temp.right;
x=x*2;
}
}
}
return x;
}
}