夯实算法-数组异或操作
题目:LeetCode
给你两个整数,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
解题思路
利用按位异或的性质,可以使用 O(1) 的时间得到结果。
根据按位异或的性质,对于二进制表示中的特定位,如果该位出现奇数个 1 则按位异或的结果是 1,如果该位出现偶数个 1 则按位异或的结果是 0。
由于数组 nums 中的任意两个相邻元素之差都是 2,因此数组 nums 中的所有元素的奇偶性相同。
- 只有当 n 和 start 都是奇数时,按位异或的结果才是奇数,否则按位异或的结果是偶数。将一个奇数减 11 的效果是将该奇数的二进制表示的最低位 1 变成 0,其余位不变。
- 如果数组 nums 中的所有元素都是奇数,则数组 nums 中的所有元素按位异或的结果(「数组按位异或结果」)可以通过如下方式计算:将数组 nums 中的所有元素减 1,得到 n 个偶数,计算这 n 个偶数的按位异或结果,记为 x,如果 n 和 start 都是奇数则数组按位异或结果为 x+1,否则数组按位异或结果为 x。
代码实现
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)O(1)
- 时间复杂度:O(1)O(1)O(1)
转载自:https://juejin.cn/post/7171814793412608008