算法(6)- 数组异或操作

1486. 数组异或操作

力扣官网题解 L6

1. 题目

1486. 数组异或操作

难度简略 83

给你两个整数，n 和 start。

数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length。

请返回 nums 中所有元素按位异或（XOR）后失去的后果。

示例 1：

输出：n = 5, start = 0
输入：8
解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8。"^" 为按位异或 XOR 运算符。

示例 2：

输出：n = 4, start = 3
输入：8
解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.

示例 3：

输出：n = 1, start = 7
输入：7

示例 4：

输出：n = 10, start = 5
输入：2

提醒：

• 1 <= n <= 1000
• 0 <= start <= 1000
• n == nums.length

2. 题解

2.1 办法一：模仿

思路

依照题意模仿即可：

代码

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

复杂度剖析

• 工夫复杂度：O(n)。这里用一重循环对 n 个数字进行异或。
• 空间复杂度：O(1)。这里只是用了常量级别的辅助空间。

2.2 办法二：数学

记 ⊕ 为异或运算，异或运算满足以下性质：

1. x⊕x=0；
2. x⊕y=y⊕x（交换律）；
3. (x⊕y)⊕z=x⊕(y⊕z)（结合律）；
4. x⊕y⊕y=x（自反性）；
5. ∀i∈Z，有 4i⊕(4i+1)⊕(4i+2)⊕(4i+3)=0。

在本题中，咱们须要计算 start⊕(start+2i)⊕(start+4i)⊕⋯⊕(start+2(n−1))。

察看公式能够晓得，这些数的奇偶性质雷同，因而它们的二进制示意中的最低位或者均为 1，或者均为 0。于是咱们能够把参加运算的数的二进制位的最低位提取进去独自解决。当且仅当 start 为奇数，且 n 也为奇数时，后果的二进制位的最低位才为 1。

此时咱们能够将公式转化为 (s⊕(s+1)⊕(s+2)⊕⋯⊕(s+n−1))×2+e，其中 s=start/2，e 示意运算后果的最低位。即咱们独自解决最低位，而舍去最低位后的数列恰成为一串间断的整数。

这样咱们能够形容一个函数 sumXor(x)，示意 0⊕1⊕2⊕⋯⊕x。利用异或运算的性质 5，咱们能够将计算该函数的复杂度升高到 O(1)，因为以 4i 为结尾的间断四个整数异或的后果为 0，所以 sumXor(x) 能够被示意为：

$$
\text{sumXor}(x)= \begin{cases} x,& x=4k,k\in Z\\ (x-1) \oplus x,& x=4k+1,k\in Z\\ (x-2) \oplus (x-1) \oplus x,& x=4k+2,k\in Z\\ (x-3) \oplus (x-2) \oplus (x-1) \oplus x,& x=4k+3,k\in Z\\ \end{cases}
$$

咱们能够进一步化简该式：

$$
\text{sumXor}(x)= \begin{cases} x,& x=4k,k\in Z\\ 1,& x=4k+1,k\in Z\\ x+1,& x=4k+2,k\in Z\\ 0,& x=4k+3,k\in Z\\ \end{cases}
$$

这样最初的后果即可示意为:

$$
(\text{sumXor}(s-1) \oplus \text{sumXor}(s+n-1))\times 2 + e)
$$

代码

class Solution {public int xorOperation(int n, int start) {
        int s = start >> 1, e = n & start & 1;
        int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
        return ret << 1 | e;
    }

    public int sumXor(int x) {if (x % 4 == 0) {return x;}
        if (x % 4 == 1) {return 1;}
        if (x % 4 == 2) {return x + 1;}
        return 0;
    }
}

复杂度剖析

• 工夫复杂度：O(1)。咱们只须要常数的工夫计算出后果。
• 空间复杂度：O(1)。咱们只须要常数的空间保留若干变量。

3. 思考

1. 首先，上面的计算公式中前两项，使用了前缀和的思路，即

   $$
   \begin{cases}
   \text{sumXor}(s-1)\quad\quad\ = 0 \oplus 1 \oplus 2 \oplus ··· \oplus {(s-2)} \oplus {(s-1)}\\
   \text{sumXor}(s+n-1)) = 0 \oplus 1 \oplus 2 \oplus ··· \oplus {(s-2)} \oplus {(s-1)} \oplus {(s)} \oplus {(s+1)} \oplus ···\oplus {(s+n-2)}\oplus {(s+n-1)}
   \end{cases}
   $$

   故，依照性质 1，这两项进行异或时，相当于做前缀和的减法，即：

$$
\text{sumXor}(s-1) \oplus \text{sumXor}(s+n-1) =[0 \oplus 1 \oplus ··· \oplus {(s-1)}] \oplus
[0 \oplus 1 \oplus ··· \oplus {(s-1)} \oplus {s} \oplus ···\oplus {(s+n-2)}\oplus {(s+n-1)}] \\
\quad\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad =[0 \oplus 0 \oplus 1 \oplus 1 \oplus ··· \oplus {(s-1)} \oplus {(s-1)}] \oplus {s} \oplus ···\oplus {(s+n-2)}\oplus {(s+n-1)}
\\ \quad\quad \quad\quad \quad\quad \quad\quad \quad\quad \quad\quad \quad\quad = {s} \oplus {(s+1)} \oplus···\oplus {(s+n-2)}\oplus {(s+n-1)}
$$

1. 对于 e 计算，则是出于以下起因点:

   对于二进制数，因为每次都是给 start 加上 2 的倍数，所以，最初失去的数组中所有数字二进制的最初一位始终是不变的，即 start 如果是偶数，则数组中所有数都是偶数，最初一位全为 0，如果是奇数，则数组中所有数都是奇数，最初一位全为 1。

   因而可知，只有 start为奇数，并且 n 为奇数时，e 的最初一位能力为 1，其余状况全为 0。

   又因为咱们只须要最初一位，所以还要按位与上 1，即：n & start & 1

2. 综合 思考 1 和 思考 2 ，咱们能够把题目做以推广，即：

   给你三个整数，n、start 和k。

   数组 nums 定义为：nums[i] = start + k*i（i 从 0 开始，k=2^m(m>=1)）且 n == nums.length。

   请返回 nums 中所有元素按位异或（XOR）后失去的后果。

   题目的解法和下面的一样，后果 result 能够示意为：

   $$
   result =\text{sumXor}(s-1) \oplus \text{sumXor}(s+n-1))\times k + e \\ 其中 s=\lfloor \frac{\textit{start}}{2} \rfloor,e=(start \% k) \oplus (start \% k) \oplus ···\oplus(start \% k)\oplus(start \% k)
   $$

   而下面的 e 等于 n 个 start 对 k 的余数异或，可参照 思考 2 ，别离对倒数第一位，倒数第二位，始终到倒数第 m 位 (k=2^m(m>=1)) 求解，再按位与即可。