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;
}
};