M个范围切换操作后的二进制数组


难度级别 中等
经常问 亚马逊 Coursera 高盛 谷歌 GreyOrange 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” 是数组中元素的数量。