【数据结构-异或字典树】力扣421. 数组中两个数的最大异或值

给你一个整数数组 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

字典树

struct Trie{
    Trie* left = nullptr;
    Trie* right = nullptr;
    Trie(){}
};


class Solution {
private:
    Trie* root = new Trie();
    static constexpr int HIGH_BIT = 30;

public:
    void add(int num){
        Trie* cur = root;
        for(int k = HIGH_BIT; k >= 0; k--){
            int bit = (num >> k) & 1;
            if(bit == 0){
                if(cur->left == nullptr){
                    cur->left = new Trie();
                }
                cur = cur->left;
            }
            else{
                if(cur->right == nullptr){
                    cur->right = new Trie();
                }
                cur = cur->right;
            }
        }
    }

    int check(int num){
        Trie* cur = root;
        int x = 0;
        for(int k = HIGH_BIT; k >= 0; k--){
            int bit = (num >> k) & 1;
            if(bit == 0){
                if(cur->right){
                    cur = cur->right;
                    x = x * 2 + 1;
                }
                else{
                    cur = cur->left;
                    x = x * 2;
                }
            }
            else{
                if(cur->left){
                    cur = cur->left;
                    x = x * 2 + 1;
                }
                else{
                    cur = cur->right;
                    x = x * 2;
                }
            }
        }
        return x;
    }

    int findMaximumXOR(vector<int>& nums) {
        int x = 0;
        for(int j = 1; j < nums.size(); j++){
            add(nums[j-1]);
            x = max(x, check(nums[j]));
        }
        return x;
    }
};

时间复杂度：O(nlogC)，其中 n 是数组 nums 的长度，C 是数组中的元素范围。

空间复杂度：O(nlogC)。每一个元素在字典树中需要使用 O(logC) 的空间，因此总空间复杂度为 O(nlogC)。

这道题我们可以使用字典树来完成，我们枚举j，然后将nums[0]到nums[j-1]的元素都加入到字典树中。

接着我们将nums[j]传入check函数中来在已经构造的字典树中找到一个最符合的路径。我们使用贪心的思想，我们要让他异或的值最大，那么就要优先在较高的bit位上找出与nums[j]对应比特位相反数值的路径。也就是说在某个比特位上，nums[j]的该比特位是1，也就是代表树中的right，那么我们就要优先走0，也就是left这条路径。如果left路径不存在的话再选择走right路径（由于cur节点存在，那么cur->left或者cur->right必定有一个存在）。只要与nums[j]某比特位相反的节点存在，那么我们就走该子树的路径，由于该比特位会是异或，所以我们的异或值x就要更新为x = x * 2 + 1，如果只存在相同比特位的节点，那么就将x更新为x = x * 2。