美文网首页
【Leetcode】1486.数组异或操作

【Leetcode】1486.数组异或操作

作者: ufogxl | 来源:发表于2022-08-04 23:45 被阅读0次

    给你两个整数,nstart
    数组 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)

    相关文章

      网友评论

          本文标题:【Leetcode】1486.数组异或操作

          本文链接:https://www.haomeiwen.com/subject/enuuwrtx.html