leetcode
leetcode 1201 ~ 1250
子数组异或查询

子数组异或查询

难度:

标签:

题目描述

代码结果

运行时间: 36 ms, 内存: 27.7 MB


import java.util.*;
import java.util.stream.*;

/**
 * Solution to calculate XOR for given ranges in queries using Java Streams.
 */
public class SolutionStream {
    /**
     * Method to find XOR from Li to Ri for each query using Streams.
     * 
     * @param arr the input array
     * @param queries the query array where each query is [Li, Ri]
     * @return an array containing the results of each query
     */
    public int[] xorQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        int[] prefixXor = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixXor[i + 1] = prefixXor[i] ^ arr[i];
        }
        return Arrays.stream(queries)
                     .mapToInt(query -> prefixXor[query[1] + 1] ^ prefixXor[query[0]])
                     .toArray();
    }
}

解释

方法:

为了高效地回答多个查询,本题解采用了前缀异或数组的技术。首先构建一个前缀数组 prefix,其中 prefix[i] 表示从 arr[0] 到 arr[i-1] 的元素的异或和。使用这个前缀数组可以在 O(1) 的时间内计算任何子数组的异或和。具体来说,子数组 arr[L] 到 arr[R] 的异或和可以表示为 prefix[R+1] ^ prefix[L],这是因为 prefix[R+1] 包含了 arr[0] 到 arr[R] 的异或结果,而 prefix[L] 包含了 arr[0] 到 arr[L-1] 的异或结果,两者异或后刚好可以得到 arr[L] 到 arr[R] 的异或结果。

时间复杂度:

O(n + q)

空间复杂度:

O(n + q)

代码细节讲解

🦆
在构建前缀异或数组时,为什么需要初始化prefix数组的长度为n+1而不是n?
初始化prefix数组的长度为n+1而不是n是为了方便处理边界情况,特别是当子数组的起始索引L为0时。prefix数组中的每个元素prefix[i]代表从数组arr的开始到arr[i-1]的元素的异或和。因此,prefix[0]需要被设为0,这样可以直接使用prefix[R+1]来获取从arr[0]到arr[R]的异或和。如果只初始化为n,那么计算从arr[0]到arr[R]的异或和时,需要做额外的条件判断,增加了复杂度。
🦆
如何理解前缀异或数组中prefix[i]的计算方法,尤其是为什么使用prefix[i-1] ^ arr[i-1]?
前缀异或数组中prefix[i]的计算方法是将前一个元素的前缀异或结果prefix[i-1]与当前数组元素arr[i-1]进行异或。这种方法的理解基于异或运算的性质:任何数与自身异或的结果为0且异或运算具有交换律和结合律。通过使用prefix[i-1] ^ arr[i-1],我们实际上是将arr[0]到arr[i-2]的异或结果与arr[i-1]进行异或,从而得到从arr[0]到arr[i-1]的所有元素的异或和,这样可以递归地构建整个prefix数组。
🦆
前缀异或数组的边界条件是如何处理的,特别是为何prefix[0]被初始化为0有助于计算子数组的异或结果?
在构建前缀异或数组时,prefix[0]被初始化为0是关键的边界条件处理方式。这是因为prefix[0]代表了空子数组的异或结果,也即没有任何元素的异或结果应为0。这样的初始化使得当我们需要计算从arr[0]到某个元素arr[R]的异或和时,可以直接使用prefix[R+1],因为prefix[R+1]实际上包含了arr[0]到arr[R]的异或结果。如果没有将prefix[0]初始化为0,那么在计算整个数组的异或结果时就需要特别处理这种情况。
🦆
在查询处理中,为什么得出子数组arr[L]到arr[R]的异或和可以通过prefix[R+1] ^ prefix[L]计算得到?
这个计算方式基于异或运算的性质,特别是异或运算的撤销性质(任何数与自身异或结果为0)和结合律。prefix数组中,prefix[R+1]代表从arr[0]到arr[R]的元素的异或结果,而prefix[L]代表从arr[0]到arr[L-1]的元素的异或结果。当使用prefix[R+1] ^ prefix[L]时,arr[0]到arr[L-1]的部分被“撤销”,只留下arr[L]到arr[R]的异或和。这样我们可以在常数时间O(1)内得到任意子数组的异或结果,极大地提高了查询效率。

相关问题