Низа на разлика | Барање за ажурирање на опсегот во О (1)


Ниво на тешкотија Тешко
Често прашувано во Арцесиум CodeNation Директи Expedia Google Квалком
Низа Проблем со пребарување

Ти е даден број низа и два вида пребарувања, едниот е да додадеме даден број во опсег, а другиот да ја отпечати целата низа. Проблемот „Низа на разлики | Барање за ажурирање на опсегот во О (1) ”бара од нас да извршиме ажурирања на опсегот во О (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}

Потоа повторно ќе ја испечатиме целата низа.

Двете групи на вредности ќе бидат отпечатени по извршувањето на пребарувањата.

Низа на разлика | Барање за ажурирање на опсегот во О (1)

 

Алгоритам за низа на разлики

  1. Создадете низа со иста големина како и дадената низа.
  2. Иницијализирајте го првиот индекс како што е даден првиот елемент на низата, а последниот индекс со 0. И сите други индекси се полни со разлика на струјата и претходниот елемент.
  3. За секое барање за ажурирање, додадете ја вредноста X на дадениот лев индекс на креираната низа и одземете X од десниот индекс на креираната низа.
  4. За секое барање за печатење, прво ја пополнуваме низата за внесување користејќи ја формулата A [i] = D [i] + A [i-1]. Потоа отпечатете ги вредностите.

Објаснување

Со оглед на низа и број и два типа на пребарувања. Значи, мора да ги извршиме двата вида пребарувања. Haveе имаме два броја што претставуваат опсег заедно со бројот X. Значи, нашата задача е да го додадеме бројот X на сите индекси помеѓу дадениот опсег. Еден од методите може да биде користење наивен пристап. За тоа, поминете ја дадената низа секој пат кога и да треба да ги ажурираме вредностите.

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

Theе ги добиеме вредностите како опсег, ако добиеме барање за ажурирање. Заедно со нас, исто така, се предвидени со голем број. Тогаш ќе го додадеме тој број на левиот индекс од низата во разликата во низата. Слично одземете ја вредноста X од десниот индекс на низата разлика. За печатење на низата ќе поминеме низ низата и за нултата индексна вредност ќе ја ажурираме вредноста на дадената низа како низата што ја создадовме, инаку ќе ја добиеме збирот на креираната низа и претходната вредност на дадената низа и отпечатете ја таа вредност за конкретниот индекс.

Код

Имплементација во C ++ за низата разлики

#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

Имплементација во Јава за низа на разлики

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

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

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

О (q) каде "Q" е бројот на пребарувања за печатење извршени како што трае пребарувањето за ажурирање О (1) време.

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

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