2025-04-11：查询子数组最大异或值。用go语言，给定一个由 n 个整数组成的数组 nums，以及一个大小为 q 的二维数

福大大架构师每日一题

发布于 2025-04-11 05:54:24

5800

代码可运行

运行总次数：0

代码可运行

2025-04-11：查询子数组最大异或值。用go语言，给定一个由 n 个整数组成的数组 nums，以及一个大小为 q 的二维数组 queries，其中每个查询 queries[i] = [li, ri] 要求在 nums[li..ri] 范围内找到任意子数组的最大异或值。

数组的异或值是通过对数组 a 进行以下操作实现的：对于所有除最后一个元素之外的元素 a[i] ，将其替换为 a[i] XOR a[i + 1]，并移除数组的最后一个元素，当只剩下一个元素时，该元素即为异或值。

你的任务是返回一个大小为 q 的数组 answer，其中 answer[i] 表示第 i 个查询的结果。

1 <= n == nums.length <= 2000。

0 <= nums[i] <= 2147483647。

1 <= q == queries.length <= 100000。

queries[i].length == 2。

queries[i] = [li, ri]。

0 <= li <= ri <= n - 1。

输入： nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]。

输出： [12,60,60]。

解释：

在第一个查询中，nums[0..2] 的子数组分别是 [2], [8], [4], [2, 8], [8, 4], 和 [2, 8, 4]，它们的异或值分别为 2, 8, 4, 10, 12, 和 6。查询的答案是 12，所有异或值中的最大值。

在第二个查询中，nums[1..4] 的子数组中最大的异或值是子数组 nums[1..4] 的异或值，为 60。

在第三个查询中，nums[0..5] 的子数组中最大的异或值是子数组 nums[1..4] 的异或值，为 60。

题目来自leetcode3277。

主要步骤

步骤一：理解异或值计算

在计算异或值时，对于数组 a，我们按照以下步骤处理：

• 将 a[i] 替换为 a[i] XOR a[i + 1]（即每个元素与其后一个元素进行异或操作）
• 移除数组的最后一个元素，直到数组只剩下一个元素，该元素即为异或值。

例如，对于数组 [2, 8, 4]:

• 2 XOR 8 = 10
• 8 XOR 4 = 12
• 2 XOR 8 XOR 4 = 6 最小的子数组 [2, 8, 4] 的异或值是 12。

步骤二：构建异或值矩阵

为了有效地计算每个查询的最大异或值，我们需要构建一个二维矩阵 mx，其中 mx[i][j] 表示从 nums[i] 到 nums[j] 范围内的所有子数组的最大异或值。这一矩阵的构建步骤如下：

• 初始化一个大小为 n x n 的矩阵 mx。
• 对于每个起始索引 i 从 n-1 到 0，填充矩阵：
- • 对角线元素 mx[i][i] 就是单个元素 nums[i]。
- • 对于每个 j 从 i + 1 到 n-1，继续计算范围 nums[i] 到 nums[j] 内的子数组的异或值，并更新 mx[i][j]，以便包含最大值。

步骤三：处理查询

对于每个查询 queries[i]:

• 从矩阵中查找 mx[li][ri] 的值，代表在 nums[li...ri] 范围内的最大异或值。
• 将结果存入答案数组 ans 中。

时间复杂度和空间复杂度分析

时间复杂度

• 构建异或值矩阵：构建矩阵的时间复杂度是 O(n^2)，因为我们需要遍历每对 (i, j) 来计算异或值。
• 处理查询：每个查询的处理时间为 O(1)，因此对于 q 个查询，总时间复杂度为 O(q)。

综合以上，总的时间复杂度为：O(n^2 + q)

空间复杂度

• 异或值矩阵：矩阵 mx 的空间复杂度是 O(n^2)。
• 结果数组：结果数组 ans 的空间复杂度是 O(q)。

综合以上，整体的空间复杂度为： O(n^2 + q)

总结

我们通过构建一个二维矩阵来存储每个子数组的最大异或值，使得在处理查询时仅需 O(1) 的时间。这种方法对于大的查询数目很高效，但由于需要 O(n^2) 的空间，在处理大规模数据时可能会受到限制。针对数量较小的 nums（如 <= 2000）和大量的查询仍能达到可接受的性能。

Go完整代码如下：

package main

import (
    "fmt"
)

func maximumSubarrayXor(f []int, queries [][]int) []int {
    n := len(f)
    mx := make([][]int, n)
    for i := n - 1; i >= 0; i-- {
        mx[i] = make([]int, n)
        mx[i][i] = f[i]
        for j := i + 1; j < n; j++ {
            f[j] ^= f[j-1]
            mx[i][j] = max(f[j], mx[i+1][j], mx[i][j-1])
        }
    }

    ans := make([]int, len(queries))
    for i, q := range queries {
        ans[i] = mx[q[0]][q[1]]
    }
    return ans
}

func main() {
    nums := []int{2, 8, 4, 32, 16, 1}
    queries := [][]int{{0, 2}, {1, 4}, {0, 5}}
    results := maximumSubarrayXor(nums, queries)
    fmt.Println(results)
}

Python完整代码如下：

# -*-coding:utf-8-*-

defmaximum_subarray_xor(f, queries):
    n = len(f)
    mx = [[0] * n for _ inrange(n)]
    
    for i inrange(n - 1, -1, -1):
        mx[i][i] = f[i]
        for j inrange(i + 1, n):
            f[j] ^= f[j - 1]
            mx[i][j] = max(f[j], mx[i + 1][j], mx[i][j - 1])

    ans = []
    for q in queries:
        ans.append(mx[q[0]][q[1]])
    
    return ans

# 示例用法
nums = [2, 8, 4, 32, 16, 1]
queries = [[0, 2], [1, 4], [0, 5]]
results = maximum_subarray_xor(nums, queries)
print(results)