LeetCode 421. 数组中两个数的最大异或值

思路一：前缀树（Trie，推荐）

核心思路： 把所有数按二进制从高位到低位插入一棵 Trie（0/1 二叉树）。然后对于每个数 num，在 Trie 中贪心地找一条"尽量与 num 当前位不同"的路径，这样异或结果的当前位才能是 1。

为什么从高位开始？因为高位对结果的贡献更大，高位能取 1 就一定优先取 1。

classSolution{publicintfindMaximumXOR(int[]nums){// 每个数 31 位，最多 nums.length * 31 个节点（+1 给根节点）intmaxNodes=nums.length*31+1;int[][]trie=newint[maxNodes][2];// trie[u][b] 表示 u 的孩子 b 的编号，0 表示不存在intsize=1;// 根节点编号为 0，size 从 1 开始分配// 1. 把所有数字插入 Trie（从高位到低位）for(intnum:nums){intnode=0;for(inti=30;i>=0;i--){intbit=(num>>i)&1;if(trie[node][bit]==0){trie[node][bit]=size++;}node=trie[node][bit];}}// 2. 对每个数字，在 Trie 中贪心找"异或最大"的搭档intans=0;for(intnum:nums){intnode=0,cur=0;for(inti=30;i>=0;i--){intbit=(num>>i)&1;intwant=bit^1;// 希望走不同分支if(trie[node][want]!=0){cur|=(1<<i);// 该位能贡献 1node=trie[node][want];}else{node=trie[node][bit];// 只能走相同分支}}ans=Math.max(ans,cur);}returnans;}}

复杂度： 时间 O(n * 31)，空间 O(n * 31)。

思路二：按位贪心 + 前缀集合（更简洁）

核心思路： 从高位到低位逐位构造答案。假设当前答案是 ans，尝试让第 i 位变成 1（candidate = ans | (1 << i)），然后检查是否存在两个数的前缀异或恰好等于 candidate。

判定技巧：若 a ^ b = candidate，则 b = a ^ candidate，只需用 HashSet 检查即可。

classSolution{publicintfindMaximumXOR(int[]nums){intans=0,mask=0;for(inti=30;i>=0;i--){mask|=(1<<i);// 保留高 i+1 位Set<Integer>prefixSet=newHashSet<>();for(intnum:nums)prefixSet.add(num&mask);intcandidate=ans|(1<<i);// 假设第 i 位能为 1for(intprefix:prefixSet){if(prefixSet.contains(prefix^candidate)){ans=candidate;// 假设成立break;}}}returnans;}}

复杂度： 时间 O(n * 31)，空间 O(n)。

对比总结

方法 时间 空间 特点
Trie（前缀树） O(n·31) O(n·31) 面试常考，体现 Trie 结构思想
按位贪心 + HashSet O(n·31) O(n) 代码短、空间小，面试可作加分项

建议先讲清 Trie 的解法（体现对字典树结构的理解），再补充按位贪心的思路，展示对位运算的深入理解。