https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/
给你一个由非负整数组成的数组 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 - 异或
- 位运算
- 剪枝
- 双指针
- 暂无
PS：使用 JS 可以平方复杂度直接莽过。不过这个数据范围平方意味着
使用前缀树的思路和 字节跳动的算法面试题是什么难度？（第二弹） 第二题比较像，很多人的解法也是如此，我就不贴了。如果还是不懂得同学，建议先看下 421. 数组中两个数的最大异或值，基本就是一个前缀树的模板。
下面介绍一个 预处理 + 双指针的方法。
和 421. 数组中两个数的最大异或值 类似，核心一句话要记住。
不要关心 x 最后和 nums 中的谁异或了，只关心最终异或的数的每一位分别是多少。
以 nums[0,1,2,3,4], x 为 9 为例，给大家讲解一下核心原理。
具体算法：
- 首先对数据进行预处理，建立一个二维 dp 数组， dp[i][j] 是和 nums[j] 第 i 位相等的最小的数组下标。
- 为了使用双指针，我们需要对 nums 进行排序
- 接下来对每一个查询，我们调用 solve 函数计算最大的异或值。
- solve 函数内部使用双指针，比较头尾指针和 x 的异或结果。更新异或结果较小的那个即可。
classSolution: defmaximizeXor(self, nums: List[int], queries: List[List[int]]) ->List[int]: defsolve(x, m, s, e): ifnums[0] >m: return-1max_v=0foriinrange(31, -1, -1): ifnums[s] & (1<<i) ==nums[e] & (1<<i): max_v+=nums[s] & (1<<i) elifnums[dp[i][e]] <=mandx^nums[s] <x^nums[e]: max_v+=nums[e] & (1<<i) # 直接移动较小指针（s）到 dp[i][e]，其他不可能是答案s=dp[i][e] else: max_v+=nums[s] & (1<<i) # 直接移动较小指针（e）到 dp[i][e] - 1，其他不可能是答案e=dp[i][e] -1returnmax_v^xnums.sort() n=len(nums) # dp[i][j] 是和 nums[j] 第 i 位相等的最小的数组下标dp= [[0for_inrange(n)] for_inrange(32)] foriinrange(32): forjinrange(n): ifj==0or (nums[j] & (1<<i)) != (nums[j-1] & (1<<i)): dp[i][j] =jelse: dp[i][j] =dp[i][j-1] return [solve(x, m, 0, n-1) forx,minqueries]复杂度分析
- 时间复杂度：$O(max(NlogN, 32*Q))$，其中 Q 为 queries 长度,N 为 nums 长度。
- 空间复杂度：$O(32*N)$，其中 N 为 nums 长度。
