陣列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循環。 在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解決方案

陣列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

也可以看看
寶石和寶石Leetcode解決方案

現在,如果這些對的數量為奇數,則第一個偶數和最後一個奇數之間的元素的異或將為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):  由於我們沒有遍歷數組的所有元素,因此使用位操作可以在恆定時間內完成操作。

也可以看看
找到差異Leetcode解決方案

空間複雜度 

O(1):  這裡使用的額外內存也是恆定的。