# 421. 数组中两个数的最大异或值 (Medium)

## 问题描述
[421. 数组中两个数的最大异或值 (Medium)](https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/)
给你一个整数数组 `nums` ，返回 `nums[i] XOR nums[j]` 的最大
运算结果，其中 `0 ≤ i ≤ j < n` 。

**示例 1：**

```
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.
```

**示例 2：**

```
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

```

**提示：**

- `1 <= nums.length <= 2 * 10⁵`
- `0 <= nums[i] <= 2³¹ - 1`

## 解题思路
如果直接暴力，求解最大异或值，时间复杂度为 $O(n^2)$，必定会超时。

实际上，我们可以把每个数字的二进制表示看成字符串，因此可以使用 [字典树](https://blog.zwyyy456.tech/zh/posts/tech/trie/) 这一数据结构来优化求解异或值的过程。暴力情况下，求解 `nums[i]` 与其他值的异或值，需要遍历整个数组，时间复杂度为 $O(n)$，而利用字典树，我们可以将这个比较的时间复杂度从 $O(n)$ 优化为 $O(\log_2C)$，其中 $C$ 为数字的大小，$\log_2C$ 即为数字的二进制表示的位数。

如果我们要找到最大异或值，应该从数字的最高位开始比较，字典树也应该从数字的高位开始构建，由于 `0 <= nums[i] <= 2^31 - 1`，因此我们可以将 `nums[i]` 右移 `j` 位的结果插入字典树，`j` 从 $31$ 递减到 $0$。

## 代码
```cpp
class Trie {
  public:
    Trie() :
        tree_{nullptr, nullptr}, end_(false) {
    }
    void Insert(int num) {
        Trie *node = this;
        for (int i = 31; i >= 0; --i) {
            int idx = ((num >> i) & 1);
            if (node->tree_[idx] == nullptr) {
                node->tree_[idx] = new Trie();
            }
            node = node->tree_[idx];
        }
        node->end_ = true;
    }
    int Count(int x) {
        Trie *node = this;
        int res = 0;
        for (int i = 31; i >= 0; --i) {
            int a = (x >> i) & 1, b = 1 - a;
            if (node->tree_[b] != nullptr) {
                res |= (1 << i);
                node = node->tree_[b];
            } else {
                node = node->tree_[a];
            }
        }
        return res;
    }

  private:
    vector<Trie *> tree_;
    bool end_;
};
class Solution {
  public:
    int findMaximumXOR(vector<int> &nums) {
        int res = 0;
        Trie *tree = new Trie();
        for (auto num : nums) {
            tree->Insert(num);
        }
        for (auto num : nums) {
            res = max(res, tree->Count(num));
        }
        return res;
    }
};
```