给你一个整数数组求任意两数异或的最大值。暴力是O(n²)——n 10⁵时就是10¹⁰次运算必死。这道题的妙处在于它看起来是“位运算题”解法却是数据结构 贪心的双剑合璧——把每个整数写成31位二进制串插进一棵只有0/1两条分支的二进制 Trie查询时对每一位贪心地往“相反”的分支走因为异或要最大该位就该是1。于是复杂度从O(n²)降到O(32n) ≈ O(n)。今天是Trie的结构贪心的一次合体演出也是“换一种编码方式就能复用旧结构”的最佳示范。 题目速览 LeetCode 42130秒读懂给你一个整数数组nums返回nums[i] XOR nums[j]的最大运算结果。示例[3,10,5,25,2,8]→ 输出285 XOR 25 28示例[0]→ 输出0示例[2,4]→ 输出6进阶要求设计一个O(n)时间算法。约束n ≤ 2×10⁵nums[i] ≤ 2³¹−1。 核心思路Trie找对手贪心定高位关键洞察按位决策高位优先异或结果是一个32位整数要让结果最大就得让高位尽可能为1——这是由二进制的权重结构决定的第k位的权重2^k大于它后面所有位的权重之和2^k − 1。所以只要某一位能取1就绝不能为了后面几位而放弃它。贪心策略从最高位到最低位逐位确定每一位都尽力取1。问题来了怎么快速知道“有没有一个数能让第k位异或结果为1”答案就是Trie。把所有数的二进制串从高位到低位插入一棵二叉树走到某一位时两条分支分别代表“这一位是0的数集合”和“这一位是1的数集合”想让x在这一位的异或结果为1就要找与x这一位相反的数于是优先走相反分支want 1 - b走不通才走相同分支算法骨架① 求数组最大值定出最高有效位high ② 把所有数从high位到0位插入二进制Trie ③ 对每个数x在树里走一遍贪心相反分支得到候选最大值 ④ 所有候选取 max 即答案一句话核心Trie负责“O(32) 找到让某位为1的对手”贪心负责“证明从高位往低位贪是对的”。贪心正确性的严格证明有人质疑“你在第k位选了相反分支可万一那条分支里的数在低位上全都吃亏呢”用一次大小比较就能封死。设第k位为分界把结果写成高位部分 第 k 位 低位部分方案A第k位取1结果 ≥prefix 2^k方案B第k位取0结果 ≤prefix 2^k − 1于是A B恒成立与低位长什么样完全无关。这就是“决策包容性”——我能做到的最优已经包含了对方所有可能。兜底保证Trie里“走不通才走相同分支”这条规则保证了任何一步都有路可走至少b分支一定存在因为x自己就插在树里所以贪心过程永远能走到叶子产出一个合法的数对。️ 图解算法手把手走一遍nums [3, 10, 5, 25, 2, 8]最大值25 11001位宽5high 4数值5位二进制30001110010105001012511001200010801000插入后Trie的每个节点代表“某个二进制前缀对应的数集合”路径前缀对应的数03, 10, 5, 2, 81250110, 8003, 5, 20003, 20015每往下走一层候选集合就缩小一圈。查询x 500101位 ix该位bwant 1−b该分支存在累计异或值401✅ 存在只有2510000 16301✅ 存在11000 24210✅ 存在1110028101❌ 不存在11100 28010❌ 不存在11100 28最终结果28即5 XOR 25 28✅ 代码实现Python JavaPythonclassSolution:deffindMaximumXOR(self,nums:list[int])-int:highmax(nums).bit_length()-1# 25 → high 4root{}# 二进制Trie# 建树从高位到低位插入forxinnums:noderootforiinrange(high,-1,-1):b(xi)1nodenode.setdefault(b,{})ans0# 查询对每个数贪心地走相反分支forxinnums:noderoot cur0foriinrange(high,-1,-1):b(xi)1want1-b# 期望该位异或为1ifwantinnode:# 有就走置位cur|(1i)nodenode[want]else:# 没有只能走相同分支nodenode[b]ansmax(ans,cur)returnansJavaclassSolution{privatestaticclassNode{Node[]childnewNode[2];// 只有0和1两条边}publicintfindMaximumXOR(int[]nums){intmax0;for(intx:nums)maxMath.max(max,x);inthigh31-Integer.numberOfLeadingZeros(max0?1:max);NoderootnewNode();for(intx:nums){// 建树Nodecurroot;for(intihigh;i0;i--){intb(xi)1;if(cur.child[b]null)cur.child[b]newNode();curcur.child[b];}}intans0;for(intx:nums){// 查询Nodecurroot;intval0;for(intihigh;i0;i--){intb(xi)1;intwant1-b;if(cur.child[want]!null){val|(1i);curcur.child[want];}else{curcur.child[b];}}ansMath.max(ans,val);}returnans;}}⚠️防坑提醒必看Java里用无符号右移别用。max 0时numberOfLeadingZeros(0) 32会让high -1需要兜底成1。Python的setdefault(b, {})比先判断再赋值更简洁。 对照解法不建树的“逐位HashSet”既然“某位能不能取1”本质是问集合里有没有某个前缀用哈希集合就够了deffindMaximumXOR_set(nums):ans,mask0,0foriinrange(max(nums).bit_length()-1,-1,-1):mask|1i# 逐步露出更高的位prefixes{xmaskforxinnums}# 所有数的高位前缀candans|(1i)# 假设这一位能取1# a ^ b cand等价于b cand ^ aifany(cand^pinprefixesforpinprefixes):anscandreturnans同样是O(32n)同样满足进阶要求——Trie不是唯一解只是最直观、最好扩展的那个。⏱️ 复杂度分析面试必问解法时间复杂度n 2×10⁵ 时暴力双循环O(n²)约2×10¹⁰次超时二进制TrieO(n)约6.4×10⁶次飞快逐位HashSetO(n)同量级常数更小空间O(32n)最坏路径不共享时。实测Trie真的比HashSet快吗n 20,000、数值0~2³⁰ 的随机数据CPython 3.13三次最好成绩解法耗时相对逐位HashSet0.151s1.0×二进制Trie0.392s2.6×慢暴力O(n²)n40002.766s—暴力O(n²)n20000外推≈ 69s—Python里Trie反而比 HashSet慢2.6倍——因为Python的字典对象分配开销大。但量级才是主要矛盾。暴力O(n²)在 n20000时约69s差了25倍以上。Trie的可扩展性远好于HashSet。LC.1803要挂计数器、LC.1707要可持久化、Top-K异或对要带剪枝DFS——这些变体HashSet版都得重写。换语言会缩小差距。Java/C里节点是紧凑结构体没有Python的字典开销Trie常数会明显下降。一句实话Trie给你的是一个可以长成各种形状的骨架而不是这一道题的最优常数。面试时两种都答得出来并主动说明“Python下我倾向HashSet工程上我倾向Trie”是加分项。 举一反三4 道高频变体题题号题目与本题的关系LC.1707与数组中元素的最大异或值每个查询带上限需离线排序 可持久化TrieLC.1803统计异或值在范围内的数对有多少计数型变体Trie节点上挂计数器LC.208实现Trie前缀树本题的结构原型LC.1442形成两个异或相等数组的三元组数目异或前缀和 哈希 面试追问模拟提前准备惊艳全场Q1为什么从最高位开始贪心是对的因为第k位的权重2^k严格大于其后所有位权重之和2^k − 1。任何“牺牲高位换取低位全1”的方案都会更差。这属于决策包容性证明和加油站那套“局部最优可推全局最优”是同一类思路。Q2位宽怎么定固定31还是动态固定31位最省事。但动态取max(nums).bit_length() - 1更聪明——所有数的高位前导零会共用同一条路径省掉大量节点。Python用bit_length()Java用31 - Integer.numberOfLeadingZeros(max)。Q3n很小的时候还有必要建树吗不必要。建树有常数开销n 50时暴力O(n²)反而更快。这是工程直觉也是面试加分项——能说出“算法选择要看数据规模”的候选人不常见。Q4如果改成求“最小异或值”怎么改从高位开始优先走相同分支因为异或为0更小但要额外排除“自己和自己异或”的情况——可以给每个节点加计数器或者在查询时跳过同一个数。 实战小技巧刷题党必备口诀高位优先贪心走反Trie建树O(32)搞定。模板二进制Trie Node[2] 从高到低插入 查询时want 1−b。防坑Java用max0时high兜底n小直接暴力。 实际应用场景不止是刷题最大/最小异或对查询网络路由、特征匹配可持久化Trie支持“历史版本查询”高级变体LC.1707异或前缀和 Trie把“子数组异或最大值”转化为“两数最大异或” 今日思考题如果把题目改成“求最小异或值”贪心策略该怎么改提示从高位开始应优先走相同分支但要额外排除“自己和自己异或”的情况。