# 1707. 与数组中元素的最大异或值

<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 可以平方复杂度直接莽过。不过这个数据范围平方意味着 $10^(10)$ 次运算，很难想象这是怎么 AC 的。

使用前缀树的思路和 [字节跳动的算法面试题是什么难度？（第二弹）](https://lucifer.ren/blog/2020/09/06/byte-dance-algo-ex-2017/) 第二题比较像，很多人的解法也是如此，我就不贴了。如果还是不懂得同学，建议先看下 [421. 数组中两个数的最大异或值](https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/)，基本就是一个前缀树的模板。

下面介绍一个 预处理 + 双指针的方法。

和 [421. 数组中两个数的最大异或值](https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/) 类似，核心一句话要记住。

不要关心 x 最后和 nums 中的谁异或了，**只关心最终异或的数的每一位分别是多少**。

以 nums\[0,1,2,3,4], x 为 9 为例，给大家讲解一下核心原理。

![](https://p.ipic.vip/78x7pl.jpg)

![](https://p.ipic.vip/yfoe80.jpg)

具体算法：

* 首先对数据进行预处理，建立一个二维 dp 数组， dp\[i]\[j] 是和 nums\[j] 第 i 位相等的最小的数组下标。
* 为了使用双指针，我们需要对 nums 进行排序
* 接下来对每一个查询，我们调用 solve 函数计算最大的异或值。
* solve 函数内部使用双指针，比较头尾指针和 x 的异或结果。更新异或结果较小的那个即可。

## 代码

```py
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] & (1<<i) == nums[e] & (1<<i):
                    max_v += nums[s] & (1<<i)
                elif nums[dp[i][e]] <= m and x ^ 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] - 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] & (1<<i)) != (nums[j-1] & (1<<i)): 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 长度。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/5640.maximum-xor-with-an-element-from-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.