M個範圍切換操作後的二進制數組


難度級別
經常問 亞馬遜 Coursera 高盛 谷歌 灰色橙色 Snapchat
排列 查詢問題

您將獲得一個二進制數組,該數組由初始0和查詢數量Q組成。 問題語句要求切換值(將0s轉換為1s,將1s轉換為0s)。 執行完Q查詢後,打印結果數組。

arr[] = {0, 0, 0, 0, 0}

Toggle(2,4)

Toggle(1,2)

Toggle(3,5)
1 0 0 0 1

解釋

第一次切換   0,1,1,1,0

第二次切換 1,0,1,1,0

第三次切換 1,0,0,0,1

M個範圍切換操作後的二進制數組

算法

  1. 創建一個n + 2大小的布爾數組。
  2. 將每個索引的布爾數組初始化為false。
  3. 現在,對於每個查詢,將元素向左和向右索引+1。
  4. 現在,只需將數組填充為前綴xor數組即可。 將所有從索引1到i的元素的異或存儲在索引i處。
  5. 打印數組

M範圍切換操作後的二進制數組的說明

給定二進制 排列,由0和1組成,顧名思義。 但是最初,它只包含0值。 給定查詢數量Q。 每個查詢包含兩個值,這些值是一個範圍的起點和一個範圍的終點,在這些範圍內,我們必須切換值,在切換意味著我們必須將0s轉換為1s,將1s轉換為0s Q數(查詢次數)。 為此,我們將創建一個 布爾 數組,其大小比數組n + 2的長度大兩倍。 然後,我們將切換值Q次,如果查詢數量更多,我們不必自己調用它,而是創建一個循環,並使用不同的查詢數量和輸入來調用它。

在切換中,將同一數組中作為範圍給出的確切位置處的值轉換為零,然後通過執行XOR操作將所有零轉換為0,然後將其轉換為零。 如果發現相同的數字或值,XOR操作對我們的作用相同,結果將為1,這意味著如果發現不同數量的值,則結果為false。 結果為XNUMX,表示為true。 因此,我們將在切換功能中執行相同的操作以反轉值。

遍歷數組,並對數組執行操作。 對數組的當前值和上一個值執行XOR操作。 我們做的事情好像發現了相同的位,否則將給出0,否則為1。此操作將是最後一次切換將成為範圍的所有值。 最後,打印數組。

推薦碼

M個範圍切換操作後在C ++中對二進制數組的實現

#include<iostream>

using namespace std;

void Toggle(bool arr[], int start, int end)
{
    arr[start] ^= 1;
    arr[end+1] ^= 1;
}

void getToggling(bool arr[], int n)
{
    for (int k=1; k<=n; k++)
        arr[k] ^= arr[k-1];
}

void printOutput(bool arr[], int n)
{
    for (int k=1; k<=n; k++)
        cout << arr[k] <<" ";
}

int main()
{
    int n = 5, m = 3;
    bool arr[n+2] = {0};

    Toggle(arr, 1, 5);
    Toggle(arr, 2, 5);
    Toggle(arr, 3, 5);

    getToggling(arr, n);

    printOutput(arr, n);
    return 0;
}
1 0 1 1 1

M個範圍切換操作後,用Java實現二進制數組

class ToggleArray
{
    static void Toggle(boolean arr[], int start, int end)
    {
        arr[start] ^= true;
        arr[end + 1] ^= true;
    }

    static void getToggling(boolean arr[], int n)
    {
        for (int k = 1; k <= n; k++)
        {
            arr[k] ^= arr[k - 1];
        }
    }

    static void printOutput(boolean arr[], int n)
    {
        for (int k = 1; k <= n; k++)
        {
            if(arr[k] == true)
                System.out.print("1" + " ");
            else
                System.out.print("0" + " ");
        }
    }

    public static void main(String args[])
    {
        int n = 5, m = 3;
        boolean arr[] = new boolean[n + 2];

        Toggle(arr, 1, 5);
        Toggle(arr, 2, 5);
        Toggle(arr, 3, 5);

        getToggling(arr, n);

        printOutput(arr, n);
    }
}
1 0 1 1 1

複雜度分析

時間複雜度

O(n + q) 哪裡 “ n” 是數組中元素的數量,“q”是查詢數。 所有查詢都在O(1)時間中執行,然後更新需要O(N)時間。

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。