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


Ниво на трудност Трудно
Често задавани в Expedia FreeCharge Google Наистина Moonfrog Labs Ola Cabs Qualtrics
Array Задача за заявка

Проблемът „Печат на модифициран масив след операции за увеличаване на обхвата на множество масиви“ гласи, че сте получили цяло число масив и са дадени „q“ номера на заявките. Дадена е и една цяло число „d“. Всяка заявка съдържа две цели числа, начална стойност и крайна стойност. Изявлението за проблем иска да разберете да увеличите всички стойности в масива в дадения диапазон със стойността „d“. Отпечатайте модифицирания масив.

Пример

arr[] = {2, 5, 1, 4, 7, 9}
Query: (1, 2), (3, 5), (4, 5), (2, 4), (1, 3)
d = 2
2 9 7 10 13 13

Обяснение

След нарастване от индекс (1,2) arr ще бъде {2, 7, 3, 4, 7, 9}

Сега нарастването от индекса (3,5) arr ще стане {2, 7, 3, 6, 9, 11}

Отново увеличение от индекс (4,5) arr ще бъде {2, 7, 3, 6, 11, 13}

Сега нарастването от индекса (2,4) arr ще стане {2, 7, 5, 8, 13, 13}

Отново увеличение от индекс (1,3) arr ще бъде {2, 9, 7, 10, 13, 13}

 

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

Алгоритъм за операции за увеличаване на обхвата на множество масиви

  1. Декларирайте масив със същия размер като дадения масив.
  2. Преминете масива от 0 до общия брой заявки.
  3. Добавете дадената стойност в масива, който създадохме, към дадения диапазон. Проверете дали крайният диапазон на дадената заявка е по-малък от дължината на масива. Ако е вярно, намалете стойността „d“ от масива, който създадохме.
  4. Прекосете дадения масив и актуализирайте изходния масив с добавяне на текущата и предишните стойности и дадения масив.
  5. Отпечатайте актуализирания масив.

Обяснение

Като се има предвид масив of цяло число и известен брой заявки, всяка заявка съдържа началния и крайния диапазон и дадена стойност. Трябва да добавим дадената стойност към всички числа от началната точка до крайната точка на дадения диапазон. Ще създаваме масив от заявки. Две от числото ще бъдат свързани с всеки от масива на заявката. Ще създадем допълнителен масив със същия размер като дължината на дадения масив. Ще извършим операциите с този масив и след това ще ги актуализираме върху дадения масив.

Сега изпълняваме цикъл до броя на заявките. Ще актуализираме изходния масив с добавяне на дадената стойност d, при началния индекс на заявката. Проверете дали крайната стойност на заявката е по-малка от дължината на масива. Ако се установи, че е истина, ако е истина, намалете d от предварително актуализираната стойност в изходния масив. Това е, за да сме сигурни, че няма да излезем извън обхвата и стойностите.

Сега ще актуализираме първата позиция на дадения масив до първата позиция на изходния масив. Тъй като ще преминем през предходните стойности на сумата (или изхода) на масива и текущата стойност. Така че вече актуализирахме първата стойност и сега преминаваме от първата позиция на изходния масив до края. Ще съберем предишната и текущата стойност и ще я съхраним в изходния масив. След това копирайте тази стойност в съответните позиции на дадения масив, докато обхождате. Отпечатайте модифицирания масив.

код

C ++ код за отпечатване на модифициран масив след операции за увеличаване на множество диапазони от масиви

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

using namespace std;

struct query
{
    int start, end;
};

void incrementByD(int arr[], struct query q_arr[],int n, int m, int d)
{
    int sum[n];
    memset(sum, 0, sizeof(sum));

    for (int i = 0; i < m; i++)
    {
        sum[q_arr[i].start] += d;

        if ((q_arr[i].end + 1) < n)
            sum[q_arr[i].end + 1] -= d;
    }
    arr[0] += sum[0];
    for (int i = 1; i < n; i++)
    {
        sum[i] += sum[i - 1];
        arr[i] += sum[i];
    }
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main()
{
    int arr[] = {2, 5, 1, 4, 7, 9};
    struct query q_arr[] = { { 1, 2 }, { 3, 5 },  {4,5 },
        { 2, 4 }, { 1, 3 }
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = sizeof(q_arr) / sizeof(q_arr[0]);

    int d = 2;

    cout << "Original Array:\n";
    printArray(arr, n);

    incrementByD(arr, q_arr, n, m, d);

    cout << "\nModified Array:\n";
    printArray(arr, n);

    return 0;
}
Original Array:
2 5 1 4 7 9
Modified Array:
2 9 7 10 13 13

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

class modifiedArray
{
    static class query
    {
        int start, end;

        query(int start, int end)
        {
            this.start = start;
            this.end = end;
        }
    }

    public static void incrementByD(int[] arr, query[] q_arr, int n, int m, int d)
    {
        int[] sum = new int[n];

        for (int i = 0; i < m; i++)
        {
            sum[q_arr[i].start] += d;

            if ((q_arr[i].end + 1) < n)
                sum[q_arr[i].end + 1] -= d;
        }
        arr[0] += sum[0];
        for (int i = 1; i < n; i++)
        {
            sum[i] += sum[i - 1];
            arr[i] += sum[i];
        }
    }

    public static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }

    public static void main(String[] args)
    {
        int[] arr = { 2, 5, 1, 4, 7, 9};
        query[] q_arr = {new query(1, 2),new query(3,5),new query(4, 5),
                  new query(2, 4),new query(1, 3)
        };

        int n = arr.length;
        int m = q_arr.length;
        int d = 2;
        System.out.println("Original Array:");
        printArray(arr, n);

        incrementByD(arr, q_arr, n, m, d);
        System.out.println("\nModified Array:");
        printArray(arr, n);
    }
}
Original Array:
2 5 1 4 7 9
Modified Array:
2 9 7 10 13 13

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

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

 O (q + n) където "н" е броят на елементите в масива и „q” е броят на заявките. Тъй като сме използвали подход като префиксна сума, имаме линейна времева сложност.

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

 О (п) където "н" е броят на елементите в масива.