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

难度: Hard

给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [x_i, m_i] 。

第 i 个查询的答案是 x_i 和任何 nums 数组中不超过 m_i 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR x_i) ，其中所有 j 均满足 nums[j] <= m_i 。如果 nums 中的所有元素都大于 m_i，最终答案就是 -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 <= 10⁵
queries[i].length == 2
0 <= nums[j], x_i, m_i <= 10⁹

Submission

运行时间: 2613 ms

内存: 162.6 MB

class Trie:
    L = 30

    def __init__(self):
        self.left = None
        self.right = None

    def insert(self, val: int):
        node = self
        for i in range(Trie.L, -1, -1):
            bit = (val >> i) & 1
            if bit == 0:
                if not node.left:
                    node.left = Trie()
                node = node.left
            else:
                if not node.right:
                    node.right = Trie()
                node = node.right
    
    def getMaxXor(self, val: int) -> int:
        ans, node = 0, self
        for i in range(Trie.L, -1, -1):
            bit = (val >> i) & 1
            check = False
            if bit == 0:
                if node.right:
                    node = node.right
                    check = True
                else:
                    node = node.left
            else:
                if node.left:
                    node = node.left
                    check = True
                else:
                    node = node.right
            if check:
                ans |= 1 << i
        return ans


class Solution:
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n, q = len(nums), len(queries)
        nums.sort()
        queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda query: query[1])
        
        ans = [0] * q
        t = Trie()
        idx = 0
        for x, m, qid in queries:
            while idx < n and nums[idx] <= m:
                t.insert(nums[idx])
                idx += 1
            if idx == 0:
                # 字典树为空
                ans[qid] = -1
            else:
                ans[qid] = t.getMaxXor(x)
        
        return ans


#-------------------------------
# class Trie:
#     def __init__(self):
#         self.num = [None,None]

#     def insert(self,nums):
#         node = self
#         for i in range(30,-1,-1):
#             n = nums>>i & 1
#             if not node.num[n]:
#                 node.num[n] = Trie()
#             node = node.num[n]

#     def search(self,nums):
#         node = self
#         ans = 0
#         for i in range(30,-1,-1):
#             ans |= 1<<i
#             cur = nums>>i & 1
#             if not node.num[1^cur]:
#                 node = node.num[cur]
#                 ans ^= 1<<i
#             else:
#                 node = node.num[1^cur]
#         return ans

# class Solution:
#     def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
#         n,q = len(nums),len(queries)
#         ans = [-1] * q
#         nums.sort()
#         target = sorted([(x,m,i) for i,(x,m) in enumerate(queries)],key = lambda x:x[1])
#         tree = Trie()
#         for x,m,i in target:
#             idx = 0
#             while idx<n and nums[idx]<=m:
#                 tree.insert(nums[idx])
#                 idx += 1
#             if idx>0:
#                 ans[i] = tree.search(x)
#         return ans

Explain

本题解的核心是使用字典树（Trie）针对整数进行位操作的优化存储。首先，将数组nums排序并对查询数组queries按m值排序以方便处理。对于每个查询（xi, mi），我们将nums中所有不大于mi的元素插入到Trie中。之后，我们使用Trie树的getMaxXor函数来找到与xi进行XOR操作可以获得的最大值。如果没有任何元素被插入到Trie中（即所有nums元素均大于mi），则返回-1。

时间复杂度: O((n + q) * L)

空间复杂度: O(nL)

class Trie:
    L = 30  # 最多30位二进制数字

    def __init__(self):
        self.left = None  # 左子树表示0
        self.right = None  # 右子树表示1

    def insert(self, val: int):
        node = self
        for i in range(Trie.L, -1, -1):  # 从高位到低位处理
            bit = (val >> i) & 1  # 获取当前位的值
            if bit == 0:
                if not node.left:
                    node.left = Trie()  # 如果左节点不存在，则创建
                node = node.left
            else:
                if not node.right:
                    node.right = Trie()  # 如果右节点不存在，则创建
                node = node.right

    def getMaxXor(self, val: int) -> int:
        ans, node = 0, self
        for i in range(Trie.L, -1, -1):
            bit = (val >> i) & 1
            check = False
            if bit == 0:
                if node.right:
                    node = node.right
                    check = True
                else:
                    node = node.left
            else:
                if node.left:
                    node = node.left
                    check = True
                else:
                    node = node.right
            if check:
                ans |= 1 << i  # 如果对应位能够匹配到期望的异或结果，设置结果位
        return ans

class Solution:
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n, q = len(nums), len(queries)
        nums.sort()  # 排序nums
        queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda query: query[1])  # 按mi排序查询
        ans = [0] * q
        t = Trie()
        idx = 0
        for x, m, qid in queries:  # 处理每一个查询
            while idx < n and nums[idx] <= m:
                t.insert(nums[idx])  # 插入符合条件的nums元素
                idx += 1
            if idx == 0:
                ans[qid] = -1  # 如果没有可用元素，返回-1
            else:
                ans[qid] = t.getMaxXor(x)  # 计算最大XOR值
        return ans

Explore

在题解中并没有特别处理数组中可能出现的重复元素，Trie树的结构本身就支持重复插入，因为即使多次插入相同的值，也只会加强Trie树中相应路径的存在性，而不会对最终的XOR查询结果产生影响。因此，可以认为Trie树处理重复元素是无害的。但是，如果业务逻辑需要避免重复计算，可以在插入前通过集合或其他结构预处理以去除重复元素。

该逻辑是通过检查在处理每个查询时Trie树中是否有元素被插入来实现的。具体实现中，使用一个索引`idx`跟踪当前已处理的`nums`元素。如果在处理某个查询（xi, mi）时，`idx`还未增加（即`idx == 0`），这意味着没有任何元素被插入到Trie树中，因为所有的nums元素都大于mi。在这种情况下，直接为该查询返回-1。

对nums进行排序的主要好处是便于高效地处理查询。在查询处理过程中，我们需要将小于等于mi的nums元素插入Trie树。如果nums是排序的，我们可以使用一个单调递增的指针来遍历nums，并停止在第一个大于mi的元素处。这种方法避免了对每个查询重复检查整个nums数组，从而提高了整体效率。

getMaxXor函数通过贪心算法确保找到最大的XOR结果。对于每一个二进制位，从最高位开始，函数尝试选择能够使得XOR结果最大化的路径。具体地，如果当前位xi为0，优先选择Trie树中的1（如果存在）；如果xi为1，则优先选择0（如果存在）。这样的选择是因为XOR操作中不同的位会产生1，从而增大结果。如果在某个位上没有可选择的路径来最大化结果，则选择可用的其他路径。通过这种方式，函数在每一位上都尽可能选取最优值，以确保最终的XOR结果是最大的。