【字典树Trie】个人练习-Leetcode-421. Maximum XOR of Two Numbers in an Array

题目链接：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/description/

题目大意：给一个数组nums[]，求最大的num[i] ^ nums[j]的值

思路：两两异或必然超时，因为二进制位就是0或1，可以用字典树来存储nums[]。往左子树走代表下一位是0，往右子树走代表下一位是1。不过有趣的是主函数中的遍历，可以把nums[0...i-1]存进Trie里，然后用nums[i]去和Trie里的树找对应，得到可能得到的最大值。

完整代码：

class Trie {
public:
    Trie* left = nullptr;
    Trie* right = nullptr;
    Trie() {}
};


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

    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 n = nums.size();
        int x = 0;
        for (int i = 1; i < n; i++) {
            add(nums[i-1]);
            // now nums[0...i-1] are in Tire
            // let nums[i] be the one to match
            x = max(x, check(nums[i]));
        }
        return x;
    }
};

时间复杂度的话，插入操作是$O(\log c)$，其中$c$是最大值。一共进行$n$次插入，复杂度为$O(n\log c)$。每一次check操作也是如此，因此复杂度为$O(n\log c)$。