算法-子数组异或查询

发表于 更新于

子数组异或查询

题目

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

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

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

  • 示例 1

输入：arr = [1, 3, 4, 8], queries = [[0, 1], [1, 2], [0, 3], [3,3]]
输出：[2, 7, 14, 8]
解释：
[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]

思路

  • 由于 a ^ 0 = a, a ^ b ^ a = b
  • 我们可以得到在区间 [i, j]上的异或
1
2
3
4
5
6
7
8
9
10
xors[j + 1] = (arr[0] ^ arr[1] ^ ... ^ arr[j]);
xors[i] = (arr[0] ^ arr[1] ^ ... ^ arr[i - 1]);
arr[i] ^ arr[i + 1] ... ^ arr[j] = s[i] ^ s[j + 1]; 

// 比如[1, 3];
arr[1] ^ arr[2] ^ arr[3];
xors[4] = arr[0] ^ arr[1] ^ arr[2] ^ arr[3];
xors[1] = arr[0];

arr[1] ^ arr[2] ^ arr[3] = xors[4] ^ xors[1];

步骤

  1. 建立xors数组保存arr前n项异或
  2. 遍历queries数组，获取所求区间[i, j]
  3. 求值 xors[i] ^ xors[j + 1]，添加到返回的数组中

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} arr
 * @param {number[][]} queries
 * @return {number[]}
 */
var xorQueries = function (arr, queries) {
    let arrLength = arr.length;
    let xors = new Array().fill(0);

    // 添加arr的前i个异或到xors的第i + 1个中
    for (let i = 0; i < arrLength; i++){
        xors[i + 1] = xors[i] ^ arr[i];
    }

    let result = [];
    queries.forEach(value => {
        // [i, j]区间异或
        result.push(xors[value[0]] ^ xors[value[1] + 1])
    });

    return result;
};