§1
题目描述
给定数组 nums,返回 nums 中任意两个数 a、b 的最大 a XOR b。异或的规则:两个二进制位相同得 0、不同得 1,所以要让高位尽量「不同」结果才大。
输入 = nums = [3,10,5,25,2,8]输出 = 28(5 XOR 25)
输入 = nums = [3,5,6]输出 = 6(3 XOR 5)
§2
思路解析动画文字版
记住「高位优先、能相反就相反」:异或的高位拉开差距最划算,所以每个数都尽量去匹配一个高位与它相反的数。下面先建树、再查询,逐帧套它。
插入 3:第 1 位 0 → 节点 0
插入 3:第 2 位 1 → 节点 01
插入 3:第 3 位 1 → 节点 011
插入 5:第 1 位 1 → 节点 1
插入 5:第 2 位 0 → 节点 10
插入 5:第 3 位 1 → 节点 101
插入 6:第 1 位 1 → 节点 1
插入 6:第 2 位 1 → 节点 11
插入 6:第 3 位 0 → 节点 110
字典树建好:3 个数各走出一条根到叶的路径
查询 3:第 1 位想走 1 → 成功,这位记 1
查询 3:第 2 位想走 0 → 成功,这位记 1
查询 3:第 3 位想走 0 → 失败,这位记 0
数 3 的最佳异或 = 6;ans = 6
查询 5:第 1 位想走 0 → 成功,这位记 1
查询 5:第 2 位想走 1 → 成功,这位记 1
查询 5:第 3 位想走 0 → 失败,这位记 0
数 5 的最佳异或 = 6;ans = 6
查询 6:第 1 位想走 0 → 成功,这位记 1
查询 6:第 2 位想走 0 → 失败,这位记 0
查询 6:第 3 位想走 1 → 成功,这位记 1
数 6 的最佳异或 = 5;ans = 6
答案:最大异或 = 6
边界:单个数答案 0;0 正常参与;全相同则异或为 0。
两个高频追问:可用逐位+哈希前缀替代字典树;位宽是常数所以接近线性。
§3
参考代码
from typing import Listclass Solution: def findMaximumXOR(self, nums: List[int]) -> int: root = {} for x in nums: node = root for b in range(31, -1, -1): bit = (x >> b) & 1 node = node.setdefault(bit, {}) ans = 0 for x in nums: node = root cur = 0 for b in range(31, -1, -1): bit = (x >> b) & 1 want = bit ^ 1 if want in node: cur |= 1 << b node = node[want] else: node = node[bit] ans = max(ans, cur) return ans看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。
§4
复杂度
- 时间：O(32n)，建树:n 个数各走 32 位;查询:n 个数各走 32 位。位宽 32 是常数,整体相当于 O(n)
- 空间：O(32n)，字典树最多 32n 个节点(每个数最坏新建一条 32 层的路径)
§5
易错点
✗ 错误写法：从低位开始贪心
✓ 正确写法：一定从最高位开始
高位的 1 比低位所有位加起来还大,必须优先把高位的异或抢成 1
✗ 错误写法：所有数补到一样长前忘了对齐位宽
✓ 正确写法：统一按固定位宽(如 32 位)取每一位
不同数二进制长度不同,不对齐高位会让比较错位
✗ 错误写法：查询时找不到相反分支就报错
✓ 正确写法：相反分支为空时退而走相同分支、这位记 0
相同位异或得 0,路要继续往下走,不能中断
§
面试追问把动画讲成自己的话
追问除了字典树,还有别的解法吗?
有。可以用「逐位 + 哈希集合」:从高位到低位逐位确定答案,假设当前答案这一位能是 1,把所有数的高位前缀放进哈希集合,检查是否存在两个前缀异或等于「期望答案」,存在就保留这一位。复杂度同样是 O(32n),思路也是高位贪心,只是把字典树换成了哈希前缀。
追问为什么时间能做到接近线性?
因为整数位宽是固定的常数(本题 32 位)。每个数无论建树还是查询,都只走固定的 32 步,所以是 O(32n),把字面上的两两枚举 O(n²) 降到了线性级别。
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
下一题 · 字典树套路 2/11
→删除子文件夹
LeetCode 1233 · 中等 · 沿着 字典树套路 继续往下推进