原题链接：421.数组中两个数的最大异或值

题目描述：

image.png

看懂题解：

暴力的匹配没有什么好说的，题目中提到进阶为O(n)，那么肯定需要在遍历到每个数 num[i] 的时候就找到和他异或值最大的数 num[j] ,并看是否能更新最大的异或值 x 。
对于每个数 num[i] ，我们选择都对他的二进制表示建一棵字典树，即下面代码中的 add 函数，当前位为0的向左建树，当前位为1的向右建树。
然后找出 num[i] 对应的最大异或值，即 check 函数:（执行前，字典树中已经包含 num[0 ~ i-1] ),取出 num[i] 的从高到低每一位，在字典树中看这一位是否有相反位存在，也就是尽可能让 x 当前位为1。
代码如下：

  1. class Solution {
  2.     // 字典树的根节点
  3.     Trie root = new Trie();
  4.     // 数据范围2^31 最高位的二进制位编号为 30 
  5.     static final int HIGH_BIT = 30;
  7.     public int findMaximumXOR(int[] nums) {
  8.         int n = nums.length;
  9.         int x = 0;
  10.         for (int i = 1; i < n; ++i) {
  11.             // 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
  12.             add(nums[i - 1]);
  13.             // 将 nums[i] 看作 ai，找出最大的 x 更新答案
  14.             x = Math.max(x, check(nums[i]));
  15.         }
  16.         return x;
  17.     }
  19.     public void add(int num) {
  20.         Trie cur = root;
  21.         for (int k = HIGH_BIT; k >= 0; --k) {
  22.             int bit = (num >> k) & 1; 
  23.             if (bit == 0) { //当前位为0则向左建树
  24.                 if (cur.left == null) {
  25.                     cur.left = new Trie();
  26.                 }
  27.                 cur = cur.left;
  28.             }
  29.             else { //为1则向右
  30.                 if (cur.right == null) {
  31.                     cur.right = new Trie();
  32.                 }
  33.                 cur = cur.right;
  34.             }
  35.         }
  36.     }
  38.     public int check(int num) {
  39.         Trie cur = root;
  40.         int x = 0; //直接计算出最大异或值
  41.         for (int k = HIGH_BIT; k >= 0; --k) {
  42.             int bit = (num >> k) & 1;
  43.             if (bit == 0) {
  44.                 // 当前位为0，需要有数这一位是1,x的这一位才能为1
  45.                 // a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
  46.                 if (cur.right != null) {
  47.                     cur = cur.right;
  48.                     x = x * 2 + 1;
  49.                 } else { // 没有那也没办法
  50.                     cur = cur.left;
  51.                     x = x * 2;
  52.                 }
  53.             } else {
  54.                 // a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
  55.                 if (cur.left != null) {
  56.                     cur = cur.left;
  57.                     x = x * 2 + 1;
  58.                 } else {
  59.                     cur = cur.right;
  60.                     x = x * 2;
  61.                 }
  62.             }
  63.         }
  64.         return x;
  65.     }
  66. }
  68. class Trie {
  69.     // 左子树指向表示 0 的子节点
  70.     Trie left = null;
  71.     // 右子树指向表示 1 的子节点
  72.     Trie right = null;
  73. }