Печатете ја изменетата низа по извршување на командите за собирање и одземање


Ниво на тешкотија Медиум
Често прашувано во ByteDance Cisco Citrix Бесплатно полнење ХакерРенк Нагаро Опера Teradata
Низа

Дадена е низа со големина n, првично сите вредности во низата ќе бидат 0, и пребарувањата. Секое пребарување ги содржи четирите вредности, типот на пребарувањето Т, левата точка на опсегот, десната точка на опсегот и бројот k, треба да ги извршите следниве операции.

Ако T = 0, додадете ја вредноста k на сите цели броеви во дадениот опсег (почеток, крај) во дадената низа,

Ако Т ​​= 1, одземете ја вредноста k од сите цели броеви во дадениот опсег (почеток, крај) во дадената низа,

пример

arr[]={0, 0, 0, 0, 0}
Query: {(0, 2, 4, 1), (1, 3, 5, 2), (0, 1, 4, 3)}
3 4 2 2 -2

Објаснување

(0, 2, 4, 1) додадете 1 на сите цели броеви во опсегот бидејќи е прашање од типот 0.

(1, 3, 5, 2) одземете 2 од сите цели броеви во опсегот бидејќи е прашање од тип 1.

(0, 1, 4, 3) додадете 3 на сите цели броеви во опсегот бидејќи е прашање од типот 0.

Печатете ја изменетата низа по извршување на командите за собирање и одземање

 

Алгоритам за печатење на модифицирана низа по повеќе прашања

  1. Иницијализира го низа со 0.
  2. За секое барање,
  3. Ако прашањето за тип треба да додаде вредности, ажурирајте ја вредноста на левата позиција 1 со додавање на вредноста k и на десната позиција одземете ја вредноста k.
  4. Ако прашањето за тип треба да ги одземе вредностите, ажурирајте ја вредноста на левата позиција 1 со одземање на вредноста k и на десната позиција додадете вредност k.
  5. Поминете низ низата и додајте ја секоја претходна вредност на тековната вредност на низата.
  6. Печатете ја последната низа.

Објаснување

Ни е дадена низа, првично, сите вредности во низата се 0. Исто така, ни се дадени a q број на пребарувања, пребарувањето ќе биде од два вида, секое пребарување содржи, неговиот тип, опсег и број k. Ако типот на пребарување е 0, ќе ја додадеме вредноста k на сите цели броеви што влегуваат во опсегот. Ако ни биде даден типот на пребарување како 1, ќе ја одземеме вредноста k од сите цели броеви, во рамките на опсегот. По извршувањето на сите пребарувања, ќе ја испечатиме таа резултат на низата.

За извршување на овие операции. Прво треба да провериме каков вид на пребарување ни е даден. Ако барањето е од прв тип, тогаш ја додаваме вредноста k на почетната точка на опсегот во низата. Исто така, одземете ја вредноста k од крајната точка на опсегот на низата.

Ние ќе го сториме спротивното од претходно споменатата техника. Ако ни се даде да користиме барање тип 1 во кое треба да ги одземеме сите вредности на цела низа во рамките. Тогаш ќе ја одземеме вредноста k од почетната вредност на низата. После тоа, додадете ја вредноста k на крајниот индекс на опсегот.

За секое дадено пребарување. Ние мора да ја изведеме споменатата техника. Тогаш ќе градиме низа, во која ќе ја додадеме претходната вредност на тековната вредност на низата. И зачувајте ја сумата до моменталната вредност. Или можеме да кажеме дека ја ажурираме тековната вредност на низата. После градење низа, ќе ја печатиме низата. Тоа ќе биде посакуваниот резултат на модифицираната низа.

Код

C ++ код за печатење на изменетата низа по извршување на командите за собирање и одземање

#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

void solveQuery(int arr[], int n, int T, int left, int right, int k)
{
    if (T == 0)
    {
        arr[left -1] += k;
        arr[right] += -k;
    }
    else
    {
        arr[left -1] += -k;
        arr[right] += k;
    }
    return;
}

void build(int arr[], int n)
{
    for (int i = 1; i < n; ++i)
        arr[i] += arr[i-1];

    return;
}

int main()
{
    int n = 5;
    int arr[n+1];

    memset(arr, 0, sizeof(arr));


    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 0, 2, 4, 1);

    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 1, 3, 5, 2);

    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 0, 1, 4, 3);

    build(arr, n);

    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    return 0;
}
3 4 2 2 -2

Java код за печатење на модифицирана низа по извршување на командите за собирање и одземање

import java.util.Arrays;

class AdditionSubtractionQuery
{
    static void solveQuery(int arr[], int n, int T, int left, int right, int k)
    {
        if (T == 0)
        {
            arr[left -1] += k;
            arr[right] += -k;
        }
        else
        {
            arr[left -1] += -k;
            arr[right] += k;
        }
        return;
    }
    
    static void build(int arr[], int n)
    {
        for (int i = 1; i < n; ++i)
            arr[i] += arr[i-1];
    }
    
    public static void main(String arg[])
    {
        int n = 5;
        int arr[] = new int[n+1];
        Arrays.fill(arr, 0);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 0, 2, 4, 1);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 1, 3, 5, 2);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 0, 1, 4, 3);

        build(arr, n);

        for (int i = 0; i < n; ++i)
            System.out.print(arr[i]+" ");
    }
}
3 4 2 2 -2

Анализа на сложеност

Временска комплексност

О (q + n) каде "Q" е бројот на пребарувања и „Н“ е бројот на елементи во низата. Бидејќи прво извршуваме Q пребарувања за кои е потребно O (1) време, а потоа за градење на низата е потребно O (N) време.

Комплексноста на просторот

Тој) каде „Н“ е бројот на елементи во низата. Бидејќи создадовме низа за извршување на операциите. Комплексноста на просторот е линеарна.