数组中两个数的最大异或值

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
private:
    static const int N = 3e6 + 1;
    int son[N][2] {0};
    int cnt = 0;
    int high;

public:
    int findMaximumXOR(vector<int>& nums) {
        build(nums);
        int res = 0;
        for (int num : nums) {
            res = max(res, maxXOR(num));
        }
        return res;
    }

    void build(const vector<int>& nums) {
        int maxNum = *max_element(nums.begin(), nums.end());
        maxNum = max(maxNum, 1);
        high = 31 - __builtin_clz(maxNum);
        for (int num : nums) {
            insert(num);
        }
    }

    void insert(int num) {
        int current = 0;
        for (int i = high; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!son[current][bit]) {
                son[current][bit] = ++cnt;
            }
            current = son[current][bit];
        }
    }

    int maxXOR(int num) {
        int res = 0, current = 0;
        for (int i = high; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int want = bit ^ 1;
            if (!son[current][want]) {
                want ^= 1;
            }
            res |= (bit ^ want) << i;
            current = son[current][want];
        }
        return res;
    }
};