Отпечатайте модифициран масив след изпълнение на командите за събиране и изваждане  


Ниво на трудност M
Често задавани в ByteDance Cisco Citrix FreeCharge Hacker Популярност Нагаро опера Терадата
Array

Получавате масив с размер n, първоначално всички стойности в масива ще бъдат 0 и заявките. Всяка заявка съдържа четирите стойности, вида на заявката T, лявата точка на диапазона, дясната точка на диапазона и число k, трябва да извършите следните операции.

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

Ако T = 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

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

Сложност във времето

O (q + n) където "Q" е броят на заявките и "н" е броят на елементите в масива. Тъй като първо изпълняваме Q заявки, които отнемат O (1) време, а след това изграждането на масива изисква O (N) време.

Вижте също
Намерете максимална дълбочина на вложените скоби в низ

Сложност на пространството

О (п) където "н" е броят на елементите в масива. Тъй като създадохме масив за изпълнение на операциите. Сложността на пространството е линейна.