题目：

思路：

• 前缀树解决，每个节点有 2 个分支：我们把数组中的每个元素看出一个 32 位的 01 串（数值不足 32 在前面补 0），将 a0~an-1 对应的 32 位二进制串插入一棵 trie 树（最低位为叶子节点）。
• insert：由于我们要求两个元素的异或最大值，所以我们肯定是要从最高位开始考虑的，因此我们存 x 时从左向右开始存储在 trie 中。
• search：我们先在 trie 树中找到能与 x 异或取得最大值的另一个数组元素 y，我们采用尽量走相反的 01 字符指针的策略，因为异或的运算的法则是相同得0，不同得1，所以我们尽可能走与 x 当前位相反的字符方向走，才能得到能和 x 产生最大值的另一个数组元素 y，然后 res=x^y。

代码如下：

class Trie
{
private:
    Trie* next[2]={nullptr};
public:
    Trie(){}

    void insert(int x)  // 在前缀树中插入值x
    {
        Trie *root=this;
        // 高位存储来Trie的前面，所以我们从左向右存储
        for(int i=30;i>=0;i--)
        {
            // 取第i位的数字，30...0
            int u=x>>i&1;
            // 若第u位为空，则创建一个新节点，然后root移动到下一个节点
            if(!root->next[u])root->next[u]=new Trie();
            root=root->next[u];
        }
    }

    int srearch(int x)  // 在前缀树中寻找 x 的最大异或值
    {
        Trie *root=this;
        // res表示最大异或值，每次res*2表示左移一位，31循环后左移了31位了，+u表示加上当前的最低位数字
        int res=0;
        for(int i=30;i>=0;i--)
        {
            int u=x>>i&1;
            // 若 x 的第 u 位存在，我们走到相反的方向去，因为异或总是|值|相反才取最大值的
            if(root->next[!u])root=root->next[!u],res=res*2+!u;
            // 相反方向的节点为空，只能顺着相同方向走了
            else root=root->next[u],res=res*2+u;
        }
        // 由于上面我们得到的异或另一个数组元素，此时我们需要将这个数组元素与x想异或得到 两个数的最大异或值
        res^=x;
        return res;
    }
};

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        Trie *root=new Trie();
        for(auto x:nums)root->insert(x);
        int res=0;
        for(auto x:nums)
            res=max(res,root->srearch(x));
        return res;
    }
};

题解2：使用haspset来代替前缀树

class Solution {
public:
  int findMaximumXOR(vector<int>& nums) {
    int mask = 0;
    int res = 0;
    for (int i = 30; i >= 0; i--)
    {
      mask = mask | (1 << i);
      unordered_set<int>sets; //这里我试过用set,会tle。。。 hash查找牛逼！！毕竟O(1)
      for (auto num : nums) {
        sets.insert(num & mask);
      }

      int temp = res | (1 << i);
      for (auto it : sets) {
        if (sets.find(it ^ temp) != sets.end()) {
          res = temp;
          break;
        }
      }
    }
    return res;
  }
};