Home LeetCode-421 Maximum XOR of Two Numbers in an Array
Post
Cancel

LeetCode-421 Maximum XOR of Two Numbers in an Array

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

struct node {
    node* next[2];
    node() { next[0]=next[1]=nullptr; }
};
struct trie {
    static const int MAXN = 2e6;
    node *root = new node();

    void add(int n) {
        node *cur = root;
        for(int i = 31; ~i; --i) {
            int c = n>>i&1;
            if(!cur->next[c]) {
                cur->next[c] = new node();
            }
            cur = cur->next[c];
        }
    }
    int query(int n) {
        int res = 0;
        node *cur = root;
        for(int i = 31; ~i; --i) {
            int c = n>>i&1;
            if(cur->next[!c]) {
                res += 1<<i;
                cur = cur->next[!c];
            } else if(cur->next[c]) {
                cur = cur->next[c];
            } else return res;
        }
        return res;
    }
};
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        trie t;
        for(auto i:nums) t.add(i);
        int res = 0;
        for(auto i:nums) res = max(res,t.query(i));
        return res;
    }
};

LeetCode-421 Maximum XOR of Two Numbers in an Array

This post is licensed under CC BY 4.0 by the author.
Contents