LeetCode LCR 067. 数组中两个数的最大异或值
题目描述
题意分析
在非负整数数组中选择两个下标，求对应元素异或的最大值。题目允许
i = j，所以可以选择同一个元素与自身异或；数组只有一个元素时，合法答案也是 $0$。每个数不超过 $2^{31}-1$，只需考虑第 $30$ 位到第 $0$ 位。两个数在某位不同，异或结果该位才为 $1$；比较结果大小时，高位权重大于全部更低位之和，因此应先确定高位。
解法：从高位试探前缀异或
核心思路
[!blue]
从最高位向最低位构造答案。已经确定的高位必须保持不变，在当前第
i位先试探能否取 $1$：把1 << i加入已有答案，得到候选flag。若存在一对原数能实现这个完整的高位候选，就应接受它，因为低位再大也弥补不了这一位从 $1$ 变成 $0$ 的损失。为只比较当前关心的高位，用
mask保留第 $30$ 位到第i位，其余位为 $0$。对每个数取value & mask，放入前缀集合；这些前缀来自原数组，因此判断它们能否配成某个异或值，就等价于判断原数能否实现相应高位。不必枚举所有前缀对。若一个前缀为
p，需要另一个前缀为q，则p ^ q == flag等价于q == p ^ flag。遍历每个p并查集合中是否存在p ^ flag，就能在线性次数的查表内完成这一轮可行性判断。每轮保持两个性质：已有答案的高位确实能由某一对输入元素实现，而且是所有数对在这些高位上的最大值。候选命中时，接受当前位的 $1$；候选未命中时，任何保留原有高位的数对都无法在这一位取 $1$，只能保留 $0$。原有高位仍有可行数对，所以不会丢失可行性。最后处理到第 $0$ 位时，高位前缀已经覆盖整个整数，答案就是实际可实现的最大异或值。
每一轮的见证数对可以不同，但
flag必须带上此前已经确定的所有高位，不能只检查当前一位。否则各位分别能实现，不代表同一对数能同时实现它们。集合只需要记录前缀是否出现，不需要计数。每轮候选都包含当前新加入的 $1$，因此
flag非零，p与p ^ flag必然不同；成功查到的两个不同前缀一定有各自的原数组元素。若所有试探都失败，返回的 $0$ 可以由同一下标实现。Go 用按位或将当前位加入
mask；Java 使用异或，但每个位只加入一次，加入前该位必为 $0$，所以两种写法在这里等价，都会逐步形成高位掩码。
解题步骤
- 初始化答案和掩码为 $0$，从第 $30$ 位向第 $0$ 位遍历。
- 将当前位加入
mask，重建所有数的高位前缀集合。- 构造
flag = 已有答案 | (1 << i)，保留旧高位并尝试当前位为 $1$。- 遍历前缀
p，若集合中存在p ^ flag，就接受flag并结束本轮；否则保留原答案。- 全部位处理完后返回答案。
代码实现
class Solution {
public int findMaximumXOR(int[] numbers) {
int max = 0;
int mask = 0;
for (int i = 30; i >= 0; i--) {
int current = 1 << i;
mask = mask ^ current;
Set<Integer> set = new HashSet<>();
for (int j = 0, k = numbers.length; j < k; j++) {
set.add(mask & numbers[j]);
}
int flag = max | current;
for (Integer prefix : set) {
if (set.contains(prefix ^ flag)) {
max = flag;
break;
}
}
}
return max;
}
}
func findMaximumXOR(nums []int) int {
ans, mask := 0, 0
for i := 30; i >= 0; i-- {
cur := 1 << i
mask |= cur
seen := make(map[int]bool, len(nums))
for _, v := range nums {
seen[v&mask] = true
}
flag := ans | cur
for p := range seen {
if seen[p^flag] {
ans = flag
break
}
}
}
return ans
}
复杂度分析
- 时间复杂度：期望 $O(Wn)$，其中
W = 31。每轮构建集合并进行至多n次哈希查询；本题位宽固定，因此满足关于元素数量的 $O(n)$ 进阶要求。- 空间复杂度：$O(n)$，每轮集合最多保存
n个不同前缀，轮次之间不保留旧集合。
关键点总结
[!green]
- 高位的 $1$ 优于所有更低位，因此从高到低试探，并以实际存在的数对验证候选。
p ^ q == flag转为查找p ^ flag，避免双重枚举。- 候选包含全部已确定高位，掩码也必须累积，不能按独立位分别拼出答案。
- 下标允许相同，零答案始终有合法来源，单元素数组无需特判。
易错点总结
[!yellow]
- 候选只保留当前位，会丢掉之前已经确定的高位约束。
- 集合保存完整原数而不是同一掩码下的前缀，会让尚未决定的低位干扰当前判断。
- 少扫第 $30$ 位会漏掉最高有效位；本题数值非负，不需要把符号位加入候选。
- 最大异或不一定包含数组最大值，不能先固定某一个数再查找另一项。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1707. 与数组中元素的最大异或值 | 困难 | 同样用二进制Trie贪心选择相反位，原题还限制参与查询的数值上界。 |