阵列Leetcode解决方案中的XOR操作


难度级别 易得奖学金
经常问 沃尔玛实验室
排列 位操作 按位异或

问题陈述

在这个问题中,我们必须在大小为n的数组中进行XOR操作,其中每个元素都等于(start + 2 * i),其中i是元素的索引(0索引),并且给定start的值。
我们必须返回数组所有元素的按位XOR。

使用案列

n = 4, start = 3
8

说明:

数组编号等于[3、5、7、9],其中(3 ^ 5 ^ 7 ^ 9)= 8。
其中“ ^”对应于按位XOR运算符。

n = 1, start = 7
7

说明:

数组num等于[7],因此xor = 7。

接近(强力)

我们可以简单地对i = 0到i = n-1运行一次for循环n次。 在for循环中,我们将与当前xor进行(start + 2 * i)的按位异或,并将其存储在变量res中。

算法

1.创建一个变量ind来表示数组元素的索引,并以0初始化。
2.创建一个变量res,以在for循环中存储当前的xor并用0初始化。
3.运行从ind = 0到ind = n-1的for循环。
4.使用(start + 2 * i)即索引ind的元素对res进行按位异或,并将结果存储在res中。
5.返回结果。

阵列Leetcode解决方案中XOR操作的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

int xorOperation(int n, int start) {

    int ind=0;
    int res=0;
    for(ind=0;ind<n;ind++) res=res^(start+2*ind);

    return res;

}
int main() 
{
        int n=4;
        int start=3;
    cout<<xorOperation(n,start)<<endl;

  return 0; 
}
8

Java程序

import java.lang.*;

class XorOperation
{  
    public static int xorOperation(int n, int start) 
    {

        int ind=0;
        int res=0;
        for(ind=0;ind<n;ind++) res=res^(start+2*ind);

        return res;      
    }
    
    
    public static void main(String args[])
    {
        int n=4;
        int start=3;

        System.out.println(xorOperation(n,start));
        
    }
}
8

阵列Leetcode解决方案中XOR运算的复杂性分析

时间复杂度

上):  其中N是数组的给定大小。 当我们在单个for循环中遍历N个元素的数组时。 因此,时间复杂度为O(N)。

空间复杂度 

O(1):  因为除了一些变量外,我们没有使用任何额外的内存。 因此,利用的额外空间是恒定的。

方法 (位操作)

在上述问题中,我们可以看到每个下一个元素之间的差异为2。这意味着所有元素将是偶数,或者所有元素都将是奇数。 这是一个范围,但不是连续的,即具有替代值。

使用位操作,我们可以找到一个常数时间范围内具有连续元素的范围的按位异或。 让我们看看如何,然后我们将尝试将上述问题转换为以下问题:

假设范围= [3,4,5,6,7,8,9,10],我们必须在第一个元素与最后一个元素之间的范围内应用xor。

令x为任意偶数,y为xie y = x + 1旁边的数字。 我们可以很容易地分析出x和y的xor始终为1。或者每个偶数和x的奇数始终为1。 1。
i.e.   4^5=1,  6^7=1,  8^9=1

现在,如果这些对的数量为奇数,则第一个偶数和最后一个奇数之间的元素的异或将为1,否则为1。
即4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 = 1 ^ 1 ^ 1 = 1

现在我们只剩下数字3和10。因此我们的答案将是3 ^ 1 ^ 10 = 8,如下图所示:

阵列Leetcode解决方案中的XOR操作

将问题转换为连续范围的异或

在上述问题中,如果我们将每个元素之间的距离从2减少到1 右移按位 每个元素除以1(等于除以2)。 通过这样做,我们只影响元素的最后一部分。 因此,我们首先通过以下几种情况存储ans的最后一部分:

1.如果数组中的所有元素均为奇数,并且元素总数也为奇数,则lastbit = 1。
2.其他lastbit = 0。

现在,将每个元素右移1后,我们的范围变为:

start / 2,start / 2 + 1,start / 2 +2,。 。 。 。 ,开始/ 2 +(n-1)。

其中first = start / 2和last = start / 2 +(n-1)。

现在,我们可以通过在恒定时间内找到末端元素以及它们之间所有偶数对的按位异或来轻松找出该范围的异或。

找到xor之后,我们必须 按位左移 将结果加1,以获得最终答案中位的原始位置。 最后,将lastbit添加到结果中并返回。

阵列Leetcode解决方案中XOR操作的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

int xorOperation(int n, int start) {

    int lastbit;
    if(n%2==1  &&  start%2==1) lastbit=1;
    else lastbit=0;

    //after 1 right shift
    int first= start/2;
    int last= start/2+ n-1;

    int res=0;

    if(first%2==1)
    { 
        res^=first; 
        first++;
    }

    if(last%2==0)
    {
        res^=last;
        last--;
    }


    int pairs=0;            //in between pairs
    if(first<last)   pairs= (last-first+1)/2;    
    if(pairs%2==1) res^=1;   

    res<<=1;                // back to 1 left shift
    res+=lastbit;           // attaching last bit

    return res;

}
int main() 
{
        int n=4;
        int start=3;
    cout<<xorOperation(n,start)<<endl;

  return 0; 
}
8

Java程序

import java.lang.*;

class Rextester
{  
    public static int xorOperation(int n, int start) 
    {

        int lastbit;
        if(n%2==1  &&  start%2==1) lastbit=1;
        else lastbit=0;

        //after 1 right shift
        int first= start/2;
        int last= start/2+ n-1;

        int res=0;

        if(first%2==1)
        { 
            res^=first; 
            first++;
        }

        if(last%2==0)
        {
            res^=last;
            last--;
        }


        int pairs=0;            //in between pairs
        if(first<last)   pairs= (last-first+1)/2;    
        if(pairs%2==1) res^=1;   

        res<<=1;                // back to 1 left shift
        res+=lastbit;           // attaching last bit

        return res;     
    }
    
    
    public static void main(String args[])
    {
        int n=4;
        int start=3;

        System.out.println(xorOperation(n,start));
        
    }
}
8

阵列Leetcode解决方案中XOR运算的复杂性分析

时间复杂度

O(1):  由于我们没有遍历数组的所有元素,因此使用位操作可以在恒定时间内完成操作。

空间复杂度 

O(1):  这里使用的额外内存也是恒定的。