资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/【算法学习】1486. 数组异或操作（java / c / c++ / python / go /

【算法学习】1486. 数组异或操作（java / c / c++ / python / go /

ztyzz / 2133人阅读

摘要：数组定义为下标从开始且。请返回中所有元素按位异或后得到的结果。样例输入输出解释数组为，其中。为按位异或运算符。也就是只有是奇数并且是奇数的时候，最终结果的最低位才会是。

非常感谢你阅读本文~
欢迎【?点赞】【⭐收藏】【?评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子 https://le-yi.blog.csdn.net/ 博客原创~

文章目录

1486. 数组异或操作：

给你两个整数，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(n)，是否有时间复杂度为O(1)的算法呢？

记x为变量，^是异或操作，则异或运算满足以下性质：

  1. x ^ x = 0；
  2. x ^ 0 = x；
  3. x ^ y = y ^ x（交换律）；
  4. (x ^ y) ^ z = x ^ (y ^ z)（结合律）；
  5. x ^ y ^ y = x（自反性）；
  6. 如果x是4的倍数，x ^ (x + 1) ^ (x + 2) ^ (x + 3) = 0；
  • 本题要计算的 结果公式 为：start ^ (start + 2) ^ (start + 4) ^ ⋯ ^(start + 2 * (n − 1))。
  • 如果有一个函数 sumXor(x) 可以计算 0 ^ 1 ^ 2 ^ ⋯ ^ x 。
  • 对于某变量x和n，计算sumXor(s - 1) ^ sumXor(s + n - 1)的结果，根据上面的 性质1 可以将 0 ^ 1 ^ 2 ^ … ^ (s - 1) 的值抵消为0，就变成 0 ^ s ^ (s + 1) ^ (s + 2) ^ ⋯ ^ (s + n - 1) ，根据 性质2 可知与0做异或操作还是自己，最后结果就变成 s ^ (s + 1) ^ (s + 2) ^ ⋯ ^ (s + n - 1) ，这个结果很接近我们要计算的内容。
  • 如果我们令 s = start / 2 ，把 结果公式 转换成 (s ^ (s + 1) ^ (s + 2) ^ ⋯ ^ (s + n - 1)) * 2，这样并不成立，因为在做除以2的操作时，最低位丢失了，但是我们可以多带带处理最低位。
  • 观察 结果公式 可知 (start + 2)，(start + 4) ，… ，(start + 2 * (n − 1)) 的奇偶性质相同，而且和start一致，也就是最低位要么都是0，要么都是1，只有基数个1做异或操作时才会是1。也就是只有start是奇数并且n是奇数的时候，最终结果的最低位 e 才会是1。
  • 这时 结果公式 可以转化为： ((sumXor(s - 1) ^ sumXor(s + n - 1)) * 2) | e 。

只要我们可以实现函数sumXor(x)，那么题目计算就可以做到O(1)的时间复杂度，根据 性质6 和 性质2 我们只需要考虑x除以4的余数，也就是最低2位，可以得到如下推导：

x % 4 = 0 的二进制位：xx…x00
x % 4 = 1 的二进制位：xx…x01
x % 4 = 2 的二进制位：xx…x10
x % 4 = 3 的二进制位：xx…x11

  • x % 4 = 0，sumXor(x) = x；
  • x % 4 = 1，sumXor(x) = (x - 1) ^ x，简化可得 sumXor(x) = 1；
  • x % 4 = 2，sumXor(x) = (x - 2) ^ (x - 1) ^ x，简化可得 sumXor(x) = x | 1；
  • x % 4 = 3，sumXor(x) = 0；
  • x % 4 等同于 x & 3 的操作，而且理论上 & 操作要比 % 操作更快；

题解

java

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) {        switch (x & 3) {            case 0:                return x;            case 1:                return 1;            case 2:                return x | 1;            default:                // x & 3 == 3                return 0;        }    }}

c

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;}int sumXor(int x) {    switch (x & 3) {        case 0:            return x;        case 1:            return 1;        case 2:            return x | 1;        default:            // x & 3 == 3            return 0;    }}

c++

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;    }    int sumXor(int x) {        switch (x & 3) {            case 0:                return x;            case 1:                return 1;            case 2:                return x | 1;            default:                // x & 3 == 3                return 0;        }    }};

python

class Solution:    def xorOperation(self, n: int, start: int) -> int:        def sumXor(x):            if x % 4 == 0:                return x            if x % 4 == 1:                return 1            if x % 4 == 2:                return x | 1            return 0        s = start >> 1        e = n & start & 1        ans = sumXor(s - 1) ^ sumXor(s + n - 1)        return ans << 1 | e

go

func xorOperation(n, start int) (ans int) {    s, e := start>>1, n&start&1    ret := sumXor(s-1) ^ sumXor(s+n-1)    return ret<<1 | e}func sumXor(x int) int {    switch x & 3 {        case 0:            return x        case 1:            return 1        case 2:            return x | 1        default:            return 0    }}

rust

impl Solution {   pub fn xor_operation(n: i32, start: i32) -> i32 {    let s = start >> 1;    let e = n & start & 1;    let ret = Solution::sum_xor(s - 1) ^ Solution::sum_xor(s + n - 1);    return ret << 1 | e  }  fn sum_xor(x: i32) -> i32 {    match x & 3 {      0 => x,      1 => 1,      2 => x | 1,      _ => 0    }  }}

原题传送门

GPU云服务器 云服务器 python操作数组 python数组操作 异或加密算法 c++操作数据库

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/122565.html

相关文章

  • 【算法学习】1920. 基于排列构建数组（java / c / c++ / python / go

    摘要：请你构建一个同样长度的数组，其中，对于每个，都满足。返回构建好的数组。从开始的排列是一个由到和也包含在内的不同整数组成的数组。 非常感谢你阅读本文，欢迎【?点赞...

    aisuhua 评论0 收藏0

  • SegmentFault 技术周刊 Vol.40 - 2018，来学习一门新的编程语言吧！

    摘要：入门，第一个这是一门很新的语言，年前后正式公布，算起来是比较年轻的编程语言了，更重要的是它是面向程序员的函数式编程语言，它的代码运行在之上。它通过编辑类工具，带来了先进的编辑体验，增强了语言服务。 showImg(https://segmentfault.com/img/bV1xdq?w=900&h=385); 新的一年不知不觉已经到来了，总结过去的 2017，相信小伙们一定有很多收获...

    caspar 评论0 收藏0

  • SegmentFault 技术周刊 Vol.40 - 2018，来学习一门新的编程语言吧！

    摘要：入门，第一个这是一门很新的语言，年前后正式公布，算起来是比较年轻的编程语言了，更重要的是它是面向程序员的函数式编程语言，它的代码运行在之上。它通过编辑类工具，带来了先进的编辑体验，增强了语言服务。 showImg(https://segmentfault.com/img/bV1xdq?w=900&h=385); 新的一年不知不觉已经到来了，总结过去的 2017，相信小伙们一定有很多收获...

    nihao 评论0 收藏0

  • SegmentFault 技术周刊 Vol.40 - 2018，来学习一门新的编程语言吧！

    摘要：入门，第一个这是一门很新的语言，年前后正式公布，算起来是比较年轻的编程语言了，更重要的是它是面向程序员的函数式编程语言，它的代码运行在之上。它通过编辑类工具，带来了先进的编辑体验，增强了语言服务。 showImg(https://segmentfault.com/img/bV1xdq?w=900&h=385); 新的一年不知不觉已经到来了，总结过去的 2017，相信小伙们一定有很多收获...

    Drummor 评论0 收藏0

  • 【算法日积月累】1-选择排序

    摘要：选择排序算法实现实现选择排序，记录最小元素的索引，最后才交换位置说明交换两个数组中的元素，在中有更简单的写法，这是的语法糖，其它语言中是没有的。和语言中比较器的实现前面我们说到了，我们为了突出排序算法的思想，将所有的例子仅限在数组排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...

    neuSnail 评论0 收藏0

发表评论

登陆后可评论

0条评论

ztyzz

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<