LeetCode 421. 数组中两个数的最大异或值思路一前缀树Trie推荐核心思路 把所有数按二进制从高位到低位插入一棵 Trie0/1 二叉树。然后对于每个数 num在 Trie 中贪心地找一条尽量与 num 当前位不同的路径这样异或结果的当前位才能是 1。为什么从高位开始因为高位对结果的贡献更大高位能取 1 就一定优先取 1。classSolution{publicintfindMaximumXOR(int[]nums){// 每个数 31 位最多 nums.length * 31 个节点1 给根节点intmaxNodesnums.length*311;int[][]trienewint[maxNodes][2];// trie[u][b] 表示 u 的孩子 b 的编号0 表示不存在intsize1;// 根节点编号为 0size 从 1 开始分配// 1. 把所有数字插入 Trie从高位到低位for(intnum:nums){intnode0;for(inti30;i0;i--){intbit(numi)1;if(trie[node][bit]0){trie[node][bit]size;}nodetrie[node][bit];}}// 2. 对每个数字在 Trie 中贪心找异或最大的搭档intans0;for(intnum:nums){intnode0,cur0;for(inti30;i0;i--){intbit(numi)1;intwantbit^1;// 希望走不同分支if(trie[node][want]!0){cur|(1i);// 该位能贡献 1nodetrie[node][want];}else{nodetrie[node][bit];// 只能走相同分支}}ansMath.max(ans,cur);}returnans;}}复杂度 时间 O(n * 31)空间 O(n * 31)。思路二按位贪心 前缀集合更简洁核心思路 从高位到低位逐位构造答案。假设当前答案是 ans尝试让第 i 位变成 1candidate ans | (1 i)然后检查是否存在两个数的前缀异或恰好等于 candidate。判定技巧若 a ^ b candidate则 b a ^ candidate只需用 HashSet 检查即可。classSolution{publicintfindMaximumXOR(int[]nums){intans0,mask0;for(inti30;i0;i--){mask|(1i);// 保留高 i1 位SetIntegerprefixSetnewHashSet();for(intnum:nums)prefixSet.add(nummask);intcandidateans|(1i);// 假设第 i 位能为 1for(intprefix:prefixSet){if(prefixSet.contains(prefix^candidate)){anscandidate;// 假设成立break;}}}returnans;}}复杂度 时间 O(n * 31)空间 O(n)。对比总结方法 时间 空间 特点Trie前缀树 O(n·31) O(n·31) 面试常考体现 Trie 结构思想按位贪心 HashSet O(n·31) O(n) 代码短、空间小面试可作加分项建议先讲清 Trie 的解法体现对字典树结构的理解再补充按位贪心的思路展示对位运算的深入理解。