题目

标题和出处

标题：数组异或操作

出处：1486. 数组异或操作

难度

1 级

题目描述

要求

给你两个整数，$\text{n}$ 和 $\text{start}$。

定义数组 $\text{nums}$，其中 $\text{nums[i]}=\text{start}+\text{2}\times \text{i}$（下标从 $\text{0}$ 开始）且 $\text{n}=\text{nums.length}$。

返回 $\text{nums}$ 中所有元素按位异或的结果。

示例

示例 1：

输入：$\text{n = 5, start = 0}$
输出：$\text{8}$
解释：数组 $\text{nums}$ 为 $\text{[0, 2, 4, 6, 8]}$，$\text{0}\oplus \text{2}\oplus \text{4}\oplus \text{6}\oplus \text{8}=\text{8}$，其中 $\oplus$ 为按位异或运算符。

示例 2：

输入：$\text{n = 4, start = 3}$
输出：$\text{8}$
解释：数组 $\text{nums}$ 为 $\text{[3, 5, 7, 9]}$，$\text{3}\oplus \text{5}\oplus \text{7}\oplus \text{9}=\text{8}$。

数据范围

• $\text{1}\le \text{n}\le \text{1000}$
• $\text{0}\le \text{start}\le \text{1000}$
• $\text{n}=\text{nums.length}$

解法一

思路和算法

最直观的方法是遍历数组 $\text{nums}$ 中的全部 $n$ 个元素，计算按位异或的结果。

由于已知 $\text{nums}[i]=\text{start}+2\times i$，且数组的长度 $n$ 和数组的首个元素 $\text{start}$ 已知，因此不需要显性创建数组，而是可以按照数组的元素值遍历。

代码

class Solution {
    public int xorOperation(int n, int start) {
        int xor = 0;
        for (int i = 0; i < n; i++) {
            xor ^= start + 2 * i;
        }
        return xor;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。需要遍历 $n$ 个元素计算按位异或的结果。

• 空间复杂度：$O(1)$。

解法二

思路和算法

利用按位异或的性质，可以使用 $O(1)$ 的时间得到结果。

根据按位异或的性质，对于二进制表示中的特定位，如果该位出现奇数个 $1$ 则按位异或的结果是 $1$，如果该位出现偶数个 $1$ 则按位异或的结果是 $0$。

由于数组 $\text{nums}$ 中的任意两个相邻元素之差都是 $2$，因此数组 $\text{nums}$ 中的所有元素的奇偶性相同。只有当 $n$ 和 $\text{start}$ 都是奇数时，按位异或的结果才是奇数，否则按位异或的结果是偶数。将一个奇数减 $1$ 的效果是将该奇数的二进制表示的最低位 $1$ 变成 $0$，其余位不变。如果数组 $\text{nums}$ 中的所有元素都是奇数，则数组 $\text{nums}$ 中的所有元素按位异或的结果（以下简称「数组按位异或结果」）可以通过如下方式计算：将数组 $\text{nums}$ 中的所有元素减 $1$，得到 $n$ 个偶数，计算这 $n$ 个偶数的按位异或结果，记为 $x$，如果 $n$ 和 $\text{start}$ 都是奇数则数组按位异或结果为 $x+1$，否则数组按位异或结果为 $x$。

首先根据 $n$ 和 $\text{start}$ 的奇偶性得到数组按位异或结果的奇偶性，如果 $\text{start}$ 是奇数则将 $\text{start}$ 的值减 $1$，然后计算 $n$ 个连续偶数的按位异或结果。

根据按位异或的性质，对于任意非负整数 $k$，$8k\oplus (8k+2)\oplus (8k+4)\oplus (8k+6)=0$，因此对于任意非负偶数 $\text{num}$，可以根据 $\text{num}$ 除以 $8$ 的余数快速计算范围 $[0,\text{num}]$ 中的所有偶数的按位异或结果。

• 如果 $\text{num}$ 除以 $8$ 的余数是 $0$，则从 $0$ 到 $\text{num}-2$ 的所有偶数为若干组 $[8k,8k+6]$，因此范围 $[0,\text{num}-2]$ 中的所有偶数的按位异或结果是 $0$，$[0,\text{num}]$ 中的所有偶数的按位异或结果是 $\text{num}$。

• 如果 $\text{num}$ 除以 $8$ 的余数是 $2$，则范围 $[0,\text{num}-4]$ 中的所有偶数的按位异或结果是 $0$，$[0,\text{num}]$ 中的所有偶数的按位异或结果是 $(\text{num}-2)\oplus \text{num}=2$。

• 如果 $\text{num}$ 除以 $8$ 的余数是 $4$，则范围 $[0,\text{num}-6]$ 中的所有偶数的按位异或结果是 $0$，$[0,\text{num}]$ 中的所有偶数的按位异或结果是 $(\text{num}-4)\oplus (\text{num}-2)\oplus \text{num}=(\text{num}-4)+6=\text{num}+2$。

• 如果 $\text{num}$ 除以 $8$ 的余数是 $6$，则范围 $[0,\text{num}]$ 中的所有偶数的按位异或结果是 $0$。

用 ${\text{xor}}_1$ 表示范围 $[0,\text{start}-2]$ 中的所有偶数的按位异或结果（当 $\text{start}=0$ 时 ${\text{xor}}_1=0$），用 ${\text{xor}}_2$ 表示范围 $[0,\text{start}+2\times (n-1)]$ 中的所有偶数的按位异或结果，用 $\text{xor}$ 表示范围 $[\text{start},\text{start}+2\times (n-1)]$ 中的所有偶数的按位异或结果，则 ${\text{xor}}_1$ 和 ${\text{xor}}_2$ 可以根据上述方法计算得到，$\text{xor}$ 是需要计算的结果。

由于 ${\text{xor}}_2={\text{xor}}_1\oplus \text{xor}$，因此有 $\text{xor}=\text{xor}\oplus {\text{xor}}_1\oplus {\text{xor}}_1={\text{xor}}_2\oplus {\text{xor}}_1$，即 $\text{xor}$ 的值等于 ${\text{xor}}_2\oplus {\text{xor}}_1$。

得到 $\text{xor}$ 的值之后，如果 $n$ 和 $\text{start}$ 都是奇数则返回 $\text{xor}+1$，否则返回 $\text{xor}$。

代码

class Solution {
    public int xorOperation(int n, int start) {
        int odd = n & start & 1;
        start -= start & 1;
        return getPrefixXor(start + 2 * (n - 1)) ^ getPrefixXor(start - 2) + odd;
    }

    public int getPrefixXor(int num) {
        if (num <= 0) {
            return 0;
        }
        int remainder = num % 8;
        if (remainder == 0) {
            return num;
        } else if (remainder == 2) {
            return 2;
        } else if (remainder == 4) {
            return num + 2;
        } else {
            return 0;
        }
    }
}

复杂度分析

• 时间复杂度：$O(1)$。

• 空间复杂度：$O(1)$。