求解思路
要让异或结果尽可能大，就要让高位尽可能出现1。
我们可以从最高位开始贪心，每一位都尝试让结果为1。
具体来说就是，先找到数组中最大值确定需要考虑的最高位，然后有2种解法：
第1种是用前缀树存储所有数字的二进制表示，查询时对于每个数字从高位到低位贪心地选择相反的路径（即当前位是0就找1，是1就找0），这样能保证异或结果尽可能大；
第2种是用哈希表，从高位到低位逐位确定答案，每次尝试在当前答案基础上让下一位为1，通过哈希表快速判断是否存在两个数能达成这个目标。
方法1：前缀树解法
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
public static int findMaximumXOR(int[] nums) {
build(nums);
int ans = 0;
for (int num : nums) {
ans = Math.max(ans, maxXor(num));
}
clear();
return ans;
}
public static int MAXN = 3000001;
public static int[][] tree = new int[MAXN][2];
public static int cnt;
public static int high;
public static void build(int[] nums) {
cnt = 1;
int max = Integer.MIN_VALUE;
for (int num : nums) {
max = Math.max(num, max);
}
// 计算最高有效位，忽略前导零
high = 31 - Integer.numberOfLeadingZeros(max);
for (int num : nums) {
insert(num);
}
}
public static void insert(int num) {
int cur = 1;
for (int i = high, path; i >= 0; i--) {
path = (num >> i) & 1;
if (tree[cur][path] == 0) {
tree[cur][path] = ++cnt;
}
cur = tree[cur][path];
}
}
public static int maxXor(int num) {
int ans = 0;
int cur = 1;
for (int i = high, status, want; i >= 0; i--) {
status = (num >> i) & 1;
want = status ^ 1; // 期望遇到相反的位
if (tree[cur][want] == 0) {
want ^= 1; // 如果不存在则走相同的位
}
ans |= (status ^ want) << i;
cur = tree[cur][want];
}
return ans;
}
public static void clear() {
for (int i = 1; i <= cnt; i++) {
tree[i][0] = tree[i][1] = 0;
}
}
|
方法2：哈希表解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public int findMaximumXOR(int[] nums) {
int max = Integer.MIN_VALUE;
for (int num : nums) {
max = Math.max(num, max);
}
int ans = 0;
HashSet<Integer> set = new HashSet<>();
for (int i = 31 - Integer.numberOfLeadingZeros(max); i >= 0; i--) {
int better = ans | (1 << i); // 尝试让第i位为1
set.clear();
for (int num : nums) {
num = (num >> i) << i; // 保留高位，低位清零
set.add(num);
// 如果存在 better ^ num，说明可以达成better
if (set.contains(better ^ num)) {
ans = better;
break;
}
}
}
return ans;
}
|