Description

给定一个数组\(a[]\),返回\(max\{a_i \oplus a_j\}\)

Constraints

  • \(1 \le a.length \le 2 \times 10^5\)
  • \(0 \le a_i \le 2^{31} - 1\)

Solution

01字典树,谁还记得啊

Code

class Solution {
public:
    struct Trie {
        std::vector<std::array<int, 2>> ch;
        int tot {}, root;

        int make() {
            ch.push_back({0, 0});
            return tot++;
        }

        Trie(): root(make()) {}

        void add(int v) {
            int cur = root;
            for(int i = 31; ~i; --i) {
                int who = v >> i & 1;
                if(!ch[cur][who]) {
                    ch[cur][who] = make();
                }
                cur = ch[cur][who];
            }
        }

        int query(int v) {
            int res = 0;
            int cur = root;
            for(int i = 31; ~i; --i) {
                int who = v >> i & 1;
                if(ch[cur][who^1]) {
                    res += 1<<i;
                    cur = ch[cur][who^1];
                } else if(ch[cur][who]) {
                    cur = ch[cur][who];
                } else {
                    break;
                }
            }
            return res;
        }
    };

    int findMaximumXOR(vector<int>& nums) {
        Trie trie;
        for(auto n : nums) trie.add(n);
        int mx = 0;
        for(auto n : nums) mx = max(mx, trie.query(n));
        return mx;
    }
};

LeetCode-421 Maximum XOR of Two Numbers in an Array