1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public int findMaximumXOR(int[] nums) {
int ans = 0;
Trie trie = new Trie();
for (int num : nums) {
trie.add(num);
int x = trie.getVal(num);
ans = Math.max(ans, num ^ x);
}
return ans;
}
private static class Trie {
Trie[] node = new Trie[2];
public void add(int x) {
Trie trie = this;
for (int i = 31; i >= 0; --i) {
int u = (x >> i) & 1;
if (trie.node[u] == null) {
trie.node[u] = new Trie();
}
trie = trie.node[u];
}
}
public int getVal(int x) {
Trie trie = this;
int ans = 0;
for (int i = 31; i >= 0; --i) {
int a = (x >> i) & 1, b = 1 - a;
if (trie.node[b] != null) {
ans |= (b << i);
trie = trie.node[b];
} else {
ans |= (a << i);
trie = trie.node[a];
}
}
return ans;
}
}
}
|
wechat
