问题描述 链接到标题

421. 数组中两个数的最大异或值 (Medium) 给你一个整数数组 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)$，必定会超时。

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

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

代码 链接到标题 

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;
    }
};