跳转至

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

问题描述#

给你一个由非负整数组成的数组 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

解题思路#

字典树加离线。

首先对 \(\texttt{nums}\) 从小到大排序。

再对所有的 \(\texttt{queries}\) 按照 \(m\) 从小到大排序。

然后遍历排好序的 \(\texttt{queries}\) 并将 \(\texttt{nums}\) 中小于等于 \(m\) 的数加入到 \(\texttt{trie}\) 中。

从高到低遍历 \(x\) 的二进制表示，因为是求异或最大，所以每次在 \(\texttt{trie}\) 中尽量选择相反的位。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def maximizeXor(
        self, nums: List[int], queries: List[List[int]]
    ) -> List[int]:
        n1, n2 = len(nums), len(queries)
        nums.sort()
        idx = sorted(range(n2), key=lambda i: queries[i][1])

        ans = [0] * n2
        j = 0
        root = [None, None]
        for i in idx:
            x, m = queries[i]
            if m < nums[0]:
                ans[i] = -1
                continue

            while j < n1 and nums[j] <= m:
                p = root
                mask = 1 << 30
                while mask:
                    b = 1 if nums[j] & mask else 0
                    if p[b] is None:
                        p[b] = [None, None]
                    p = p[b]
                    mask >>= 1
                j += 1

            p = root
            t = 0
            mask = 1 << 30
            while mask:
                b = 1 if mask & x else 0
                if p[b ^ 1] is not None:
                    b ^= 1
                p = p[b]
                if b:
                    t += mask
                mask >>= 1
            ans[i] = x ^ t
        return ans
返回顶部

在手机上阅读