Leetcode-1310-子数组异或查询

Leetcode-1310-子数组异或查询

题目描述

• 有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。

• 对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作为本次查询的结果。

• 并返回一个包含给定查询 queries 所有结果的数组。

输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8] 
解释：
数组中元素的二进制表示形式是：
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8


示例 2：

输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
输出：[8,0,4,4]

• 提示：
  • 1 <= arr[i] <= 10^9
  • 1 <= arr.length <= 3 * 10^4
  • encoded.length == n - 1
  • 1 <= queries.length <= 3 * 10^4
  • 0 <= queries[i][0] <= queries[i][1] < arr.length

算法思路：异或性质/前缀和

异或运算具有如下性质：

• 异或运算满足交换律和结合律；

• 任意整数和自身做异或运算的结果都等于 0，即x⊕x=0；

• 任意整数和 0 做异或运算的结果都等于其自身，即x⊕0=0⊕x=x。

依然可以考虑能否使用前缀和的思想解决本题：

• 假设有数组arr = [A, B, C, D, E],将异或运算A XOR B简记为AB，那么前缀和preXOR = [0, A, AB, ABC, ABCD, ABCDE](preXOR的第一个数值0可以认为是初始化)；
• 假设我们求 [1, 2] 区间上的区间异或，那么结果为arr[1] XOR arr[2] = BC = preXOR[2 + 1] XOR preXOR[1] = ABC XOR A = BC，至此，我们使用前缀和preXOR得到了区间异或结果。

具体来说：

class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        // 1. 计算异或前缀和
        int n = arr.length;
        int[] xors = new int[n + 1];                // 前缀和数组
        for(int i = 0;i < n;i++){                   // 计算前缀和
            xors[i + 1] = xors[i] ^ arr[i];
        }

        // 2. 计算前缀和区间查询数组
        int m = queries.length;
        int[] ans = new int[m];
        for(int i = 0;i < m;i++){                   // 区间[left,right]的前缀和
            ans[i] = xors[queries[i][0]] ^ xors[queries[i][1] + 1];
        }

        // 3. 返回结果数组
        return ans;
    }
}

复杂度分析

• 时间复杂度 ：O(n + m) , 其中n是arr的长度, m是queries的长度
• 空间复杂度 ：O(1) 注意空间复杂度不考虑返回值。

打赏