给你两个整数,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 。
示例 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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/xor-operation-in-an-array
1.暴力算法:
//javascript
var xorOperation = function(n, start) {
var ans = 0;
for(var i = 0;i < n;i++){
ans ^= (start + 2 * i);
}
return ans;
};
顺序遍历,时间复杂度O(n),空间复杂度O(1)
2.找规律解法:
相邻四个整数的异或结果为0(4n ^ 4n + 1 ^ 4n + 2 ^ 4n + 3 = 0)
对于一个差值为2等差数列,可以考虑除以差值2,转换为差值为1的等差数列,同时保存末位的异或结果, 这样只需要计算最后几项的异或值,再对结果还原后添加回末位异或结果即可。
特别地,对于数字数列的末几位4n...k的异或值(即整个数列的异或值)可以由k直接确定。
k % 4 = 0 -> k
k % 4 = 1 -> 1
k % 4 = 2 -> k + 1
k % 4 = 3 -> 0
当start为偶数时,数列中所有值的末尾都是0,因此异或值末位为0;当start为奇数时,末尾值取决于n,n为奇数时为1,为偶数时为0
e = start & n & 1
原式子各项除以2,得
(start / 2) ^ (start / 2 + 1) ^ (start / 2 + 2) ··· ^ (start / 2 + n - 1)
=
(1 ^ 2 ^ 3 ··· ^start / 2 - 1) ^ (1 ^ 2 ^ 3 ··· ^start / 2 - 1 ) ^ (start / 2) ^ (start / 2 + 1) ^ (start / 2 + 2) ··· ^ (start / 2 + n - 1)
//C
int computeXOR(int n){
switch(n % 4){
case 0: return n;
case 1: return 1;
case 2: return n + 1;
default: return 0;
}
}
int xorOperation(int n, int start){
int e = n & start & 1;
int s = start >> 1;
int ans = computeXOR(s - 1) ^ computeXOR(s + n - 1);
return (ans << 1) + e;
}
时间复杂度O(1),空间复杂度O(1)
网友评论