Различен масив | Заявка за актуализиране на обхвата в O (1)  


Ниво на трудност Трудно
Често задавани в Арцезиум CodeNation Директи Expedia Google Qualcomm
Array Задача за заявка

Вие получавате цяло число масив и два вида заявки, едната е да добавите дадено число в диапазон, а другата да отпечата целия масив. Проблемът „Различен масив | Заявка за актуализиране на диапазон в O (1) ”изисква да извършим актуализации на диапазона в O (1).

Пример  

arr[] = {20, 30, 25, 50}

Update(0, 1, 10)

print()

update(0, 2, 20)

update(2, 3, 30)

print()
(30 40 25 50) (50 60 75 80)

Обяснение

10 ще бъдат добавени към 20 и 30, така че масивът ще стане {30, 40, 25, 50}

След това ще отпечатаме целия масив.

20 ще бъдат добавени към 30, 40 и 25, така че масивът ще стане {50, 60, 45, 50}

10 ще бъдат добавени към 45 и 50, така че масивът ще стане {50, 60, 75, 80}

След това отново ще отпечатаме целия масив.

Двата набора от стойности ще бъдат отпечатани след изпълнение на заявките.

Различен масив | Заявка за актуализиране на обхвата в O (1)щифт

 

Алгоритъм за различен масив  

  1. Създайте масив със същия размер като дадения масив.
  2. Инициализирайте първия индекс като първия елемент на дадения масив, а последния индекс с 0. И всички други индекси се запълват с разлика в текущия и предишния елемент.
  3. За всяка заявка за актуализация добавете стойността X към дадения ляв индекс на създадения масив и извадете X от десния индекс на създадения масив.
  4. За всяка заявка за печат първо попълваме входния масив, използвайки формулата A [i] = D [i] + A [i-1]. След това отпечатайте стойностите.
Вижте също
Като се имат предвид два несортирани масива, намерете всички двойки, чиято сума е x

Обяснение  

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

Тук се обсъжда по-добро решение, което е да се създаде допълнителен масив, който съхранява разликата. Ето защо тя се нарича различен масив. Първо, инициализирайте първия елемент от масива за разлика като първия елемент от входния масив. След това присвояваме последния елемент от масива за разлика на 0. След това ще преминем през масива и ще съхраним разликата на текущата стойност и предишната стойност в текущия индекс в масива на разликата.

Ще получим стойностите като диапазон, ако получим заявка за актуализация. Заедно с нас ни се предоставя и номер. След това ще добавим това число в левия индекс на диапазона в различен масив. По същия начин извадете стойността X от десния индекс на различния масив. За отпечатване на масива ще преминем през масива, а за нулевата стойност на индекса ще актуализираме стойността на дадения масив като масива, който сме създали, иначе ще получим сумата от създадения масив и предишната стойност на дадения масив и отпечатайте тази стойност за конкретния индекс.

Вижте също
Брой индекси с равни елементи в даден диапазон

код  

Внедряване в C ++ за Difference Array

#include<iostream>

using namespace std;

void buildArray(int arr[], int dummyArray[], int n)
{
    dummyArray[0] = arr[0];
    dummyArray[n] = 0;
    for (int i = 1; i < n; i++)
        dummyArray[i] = arr[i] - arr[i - 1];
}

static void update(int dummyArray[], int l, int r, int x)
{
    dummyArray[l] += x;
    dummyArray[r + 1] -= x;
}

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

        if (i == 0)
            arr[i] = dummyArray[i];
        else
            arr[i] = dummyArray[i] + arr[i - 1];

        cout<<arr[i] << " ";
    }

    cout<<endl;
}

int main()
{
    int arr[] = {20,30,25,50};
    int n = sizeof(arr)/sizeof(arr[0]);

    int dummyArray[n + 1];
    buildArray(arr, dummyArray, n);

    update(dummyArray, 0, 1, 10);
    printArray(arr, dummyArray, n);
    update(dummyArray, 0, 2, 20);
    update(dummyArray, 2, 3, 30);

    printArray(arr, dummyArray,n);
    return 0;
}
30 40 25 50
50 60 75 80

Внедряване в Java за различен масив

class differenceArray
{
    static void buildArray(int arr[], int dummyArray[])
    {

        int n = arr.length;

        dummyArray[0] = arr[0];
        dummyArray[n] = 0;
        for (int i = 1; i < n; i++)
            dummyArray[i] = arr[i] - arr[i - 1];
    }
    
    static void update(int dummyArray[], int left, int right, int x)
    {
        dummyArray[left] += x;
        dummyArray[right + 1] -= x;
    }
    
    static int printArray(int arr[], int dummyArray[])
    {
        for (int i = 0; i < arr.length; i++)
        {
            if (i == 0)
                arr[i] = dummyArray[i];
            else
                arr[i] = dummyArray[i] + arr[i - 1];

            System.out.print(arr[i] + " ");
        }

        System.out.println();

        return 0;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {20, 30, 25, 50};
        int n = arr.length;
        int dummyArray[] = new int[n + 1];

        buildArray(arr, dummyArray);

        update(dummyArray, 0, 1, 10);
        printArray(arr, dummyArray);
        update(dummyArray, 0, 2, 20);
        update(dummyArray, 2, 3, 30);

        printArray(arr, dummyArray);
    }
}
30 40 25 50
50 60 75 80

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

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

O (q) където "Q" е броят на заявките за печат, изпълнени в зависимост от заявката за актуализация O (1) време.

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

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

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