Skip to content

Latest commit

 

History

History
110 lines (77 loc) · 4.13 KB

5640.maximum-xor-with-an-element-from-array.md

File metadata and controls

110 lines (77 loc) · 4.13 KB

题目地址(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 的。

使用前缀树的思路和 字节跳动的算法面试题是什么难度?(第二弹) 第二题比较像,很多人的解法也是如此,我就不贴了。如果还是不懂得同学,建议先看下 421. 数组中两个数的最大异或值,基本就是一个前缀树的模板。

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

421. 数组中两个数的最大异或值 类似,核心一句话要记住。

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

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

具体算法:

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

代码

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 长度。