力扣 1707. 与数组中元素的最大异或值预处理 双指针解法深度解析LeetCode 题解之路系列【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文基于 leetcode 仓库的 problems/5640.maximum-xor-with-an-element-from-array.md 展开围绕力扣 1707「与数组中元素的最大异或值」这道经典位运算题目完整讲解题目约束、核心思路、预处理技巧与双指针算法的正确性来源并结合仓库中 thinkings/bit.md 的异或基础与 thinkings/basic-data-structure.md 的字典树章节给出可运行的 Python 实现与复杂度分析。读完本文你将掌握两类解决带上限的最大异或问题的套路前缀树Trie模板法与预处理 双指针法并能在 O(32 × Q) 的查询时间内处理大规模数据。题目描述给你一个由非负整数组成的数组nums。另有一个查询数组queries其中queries[i] [xi, mi]。第 i 个查询的答案是xi和任何nums数组中不超过mi的元素按位异或XOR得到的最大值。换句话说答案是max(nums[j] XOR xi)其中所有j均满足nums[j] mi。如果nums中的所有元素都大于mi最终答案就是-1。返回一个整数数组answer作为查询的答案其中answer.length queries.length且answer[i]是第 i 个查询的答案。示例 1输入nums [0,1,2,3,4], queries [[3,1],[1,3],[5,6]] 输出[3,3,7] 解释 1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 3 而 1 XOR 3 2 。二者中的更大值是 3 。 2) 1 XOR 2 3. 3) 5 XOR 2 7.示例 2输入nums [5,2,4,6,6,3], queries [[12,4],[8,1],[6,3]] 输出[15,-1,5]提示1 nums.length, queries.length 105 queries[i].length 2 0 nums[j], xi, mi 109前置知识异或位运算剪枝双指针核心思路不要关心最终异或的对象只关心结果的每一位这道题最直观的暴力做法是对每个查询遍历整个nums平方复杂度在nums.length, queries.length均可达 1e5 的数据范围下意味着约 10^10 次运算。原文档作者特别指出使用 JS 可以平方复杂度直接莽过。不过这个数据范围平方意味着 10^10 次运算很难想象这是怎么 AC 的。 因此我们需要一个更聪明的做法。与力扣 421「数组中两个数的最大异或值」类似解题前要记住一句核心的话不要关心 x 最后和 nums 中的谁异或了只关心最终异或的数的每一位分别是多少。由于nums[j]与xi均不超过 1e9约 2^30我们只需要考虑二进制下 0 到 30 位共 31 位代码中从 31 遍历到 0 以覆盖边界。从高位向低位逐位贪心高位的 1 比低位的所有位加起来都值钱所以每一位都尽可能让异或结果为 1这样构造出的数就是最大异或值。异或的基础性质来自仓库位运算专题仓库 thinkings/bit.md 对异或做了系统总结是理解本题的数学基础性质两个数字异或的结果a^b是将 a 和 b 的二进制每一位进行运算得出的数字。运算的逻辑是同一位的数字相同则为 0不同则为 1。规律任何数和本身异或则为0任何数和 0 异或是本身运算满足交换律a ^ b ^ c a ^ c ^ b正是同 0 异 1的逐位性质决定了最大化异或值可以转化为逐位贪心构造结果。具体算法预处理 双指针原文档给出的方案分四步对数据进行预处理建立一个二维 dp 数组dp[i][j]是和nums[j]第i位相等的最小的数组下标。这一步是为了后续双指针移动时能跳着走——一次跳过一整段与当前位置第i位相同的连续区间。对 nums 进行排序排序后满足nums[j] mi的元素构成一个连续前缀双指针才能生效。对每一个查询调用 solve 函数计算最大的异或值。solve 函数内部使用双指针比较头尾指针与x的异或结果更新异或结果较小的那个即可。利用 dp 数组一次性把指针跳到该位相同区间的边界实现剪枝。用一句话概括双指针的正确性排序后若区间[s, e]内所有数第i位相同则这一位对任意x的异或结果都相同可以整体剪掉若第i位不同则说明区间横跨了 0/1 分界此时比较两个端点的异或结果较大的一侧保留较小的一侧直接跳到dp[i][e]分界处其余中间元素在这一位上不可能产生更优解。参考代码class Solution: def maximizeXor(self, nums: List[int], queries: List[List[int]]) - List[int]: def solve(x, m, s, e): if nums[0] m: return -1 max_v 0 for i in range(31, -1, -1): if nums[s] (1i) nums[e] (1i): max_v nums[s] (1i) elif nums[dp[i][e]] m and x ^ nums[s] x ^ nums[e]: max_v nums[e] (1i) # 直接移动较小指针s到 dp[i][e]其他不可能是答案 s dp[i][e] else: max_v nums[s] (1i) # 直接移动较小指针e到 dp[i][e] - 1其他不可能是答案 e dp[i][e] - 1 return max_v ^ x nums.sort() n len(nums) # dp[i][j] 是和 nums[j] 第 i 位相等的最小的数组下标 dp [[0 for _ in range(n)] for _ in range(32)] for i in range(32): for j in range(n): if j 0 or (nums[j] (1i)) ! (nums[j-1] (1i)): dp[i][j] j else: dp[i][j] dp[i][j-1] return [solve(x, m, 0, n-1) for x,m in queries]复杂度分析时间复杂度$O(max(NlogN, 32*Q))$其中 Q 为 queries 长度N 为 nums 长度。空间复杂度$O(32*N)$其中 N 为 nums 长度。另一条经典路线前缀树Trie原文档指出使用前缀树的思路和字节跳动的算法面试题第二题比较像很多人的解法也是如此……如果还是不懂的同学建议先看下 421. 数组中两个数的最大异或值基本就是一个前缀树的模板。前缀树路线的核心是把所有nums[j]按二进制位插入一棵二叉 Trie每一位只有 0/1 两个分支查询时从高位到低位尽量走与xi当前位相反的子树从而贪心地让每一位异或结果都为 1。针对本题不超过 mi的约束常见做法有两种离线处理把查询按mi排序同时把nums排序逐个把不超过mi的数插入 Trie再查询在线处理Trie 节点额外维护子树内的最小值查询时只进入最小值不超过mi的分支利用 1e9 2^30 的位长限制做剪枝。仓库中关于 Trie 的基础可以参考 thinkings/basic-data-structure.md 的字典树前缀树小节其中推荐了 problems/208.implement-trie-prefix-tree.md 作为前缀树的标准模板题。掌握了 208 的插入与查找结构再为节点增加最小值字段或配合离线排序即可改写出本题的 Trie 解法。两种路线的对比方案预处理单次查询空间特点前缀树离线排序排序 O(NlogN QlogQ)O(32)O(32 × N)思路通用易迁移到 421、字节面试题变体预处理 双指针本文排序 构建 dp 表 O(NlogN 32 × N)O(32)O(32 × N)无指针/节点对象开销常数更小纯数组实现总结力扣 1707 的难点不在异或本身而在不超过 mi这个附加约束。本文介绍的两条路线殊途同归贪心是灵魂从高位到低位逐位构造最大异或值这是所有解法的共同出发点剪枝是手段前缀树用子树最小值或离线排序剪枝双指针方案用 dp 表把指针直接跳到分界处剪枝预处理的 dp 表是本仓库方案的独特之处dp[i][j]记录与nums[j]第 i 位相等的最小下标让双指针一次跳跃跳过整段无效区间。该题已被收录进仓库 collections/hard.md 的困难题清单与 problems/1310.xor-queries-of-a-subarray.md前缀异或、problems/1521.find-a-value-of-a-mysterious-function-closest-to-target.md位运算单调性等题目共同构成仓库的位运算题解矩阵可作为刷题时互相印证的系列参考。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考