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

LeetCode 421. Maximum XOR of Two Numbers in an Array

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

method

将所有元素的二进制表示构建成前缀树，因为要1和0相反异或值才是1，所以对于一个数去找与他异或值最大的数时，要往与他二进制相反的那边找，而且要从高位往低位找，因为高位的比重比低位大

struct Node {
    int son[2];
};

vector<Node> node;

int findMaximumXOR(vector<int>& nums) {
    node.push_back(Node{0, 0});
    for (auto n : nums) {
        int p = 0;  // 遍历的指针
        for (int i = 31; i >= 0; i--) {
            int t = n >> i & 1;
            if (!node[p].son[t]) {
                node.push_back(Node{0, 0});
                node[p].son[t] = node.size() - 1;
            }
            p = node[p].son[t];
        }
    }   // 这样Trie树就构建完了
    int res = 0;
    for (auto n : nums) {
        int p = 0, maxn = 0;
        for (int i = 31; i >= 0; i--) {
            int t = n >> i & 1;
            if (node[p].son[!t]) {
                p = node[p].son[!t];
                maxn += 1 << i; // 如果有相反的，结果就可以增加，没有就不行了
            }
            else p = node[p].son[t];
        }
        res = max(res, maxn);
    }
    return res;
}