Айырмашылық массиві | O ауқымындағы жаңарту сұранысы (1)  


Күрделілік дәрежесі қиын
Жиі кіреді Арцезий CodeNation Directi 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 мәнін қосып, құрылған массивтің оң индексінен Х-ны алып тастаңыз.
  4. Әрбір баспа сұранысы үшін алдымен A [i] = D [i] + A [i-1] формуласын пайдаланып енгізу жиымын толтырамыз. Содан кейін мәндерді басып шығарыңыз.
Сондай-ақ, қараңыз
Берілген екі сұрыпталмаған массив қосындысы х-қа тең болатын барлық жұптарды табады

Түсіндіру  

Массив пен сан және сұраныстың екі түрі берілген. Сондықтан біз сұраныстың екі түрін орындауымыз керек. Бізде X санымен қатар ауқымды көрсететін екі сан болады, сондықтан біздің міндетіміз - берілген диапазон арасындағы барлық индекстерге X санын қосу. Әдістердің бірі аңғалдықты қолдану болуы мүмкін. Ол үшін мәндерді жаңарту қажет болған сайын берілген жиымнан өтіңіз.

Мұнда айырмашылықты сақтайтын қосымша массив құру туралы жақсы шешім талқыланады. Сондықтан оны айырым жиымы деп атайды. Алдымен айырым жиымының бірінші элементін кіріс жиымының бірінші элементі ретінде инициализациялаңыз. Содан кейін айырым жиымының соңғы элементін 0-ге тағайындаңыз. Осыдан кейін біз массив арқылы өтіп, ағымдағы мән мен алдыңғы мәннің айырмасын ағымдағы индексте айырмашылық жиымында сақтаймыз.

Жаңарту сұранысын алсақ, мәндерді ауқым ретінде аламыз. Сонымен қатар бізге нөмір беріледі. Содан кейін біз бұл санды айырым жиымының диапазонының сол жақ индексіне қосамыз. Сол сияқты айырым жиымының оң индексінен Х мәнін алып тастаңыз. Массивті басып шығару үшін біз массивті айналып өтеміз және нөлдік индекс мәні үшін берілген массивтің мәнін біз құрған массив ретінде жаңартамыз, әйтпесе біз құрылған массивтің қосындысын және берілген массивтің алдыңғы мәнін аламыз және белгілі бір индекс үшін осы мәнді басып шығарыңыз.

Сондай-ақ, қараңыз
Берілген диапазонда элементтері тең индекстер саны

код  

Айырмашылық массивіне арналған 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

Айырмашылық массивіне арналған 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) уақыт.

Сондай-ақ, қараңыз
Айқын элементтері бар ішкі массивтер

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны. Біз қосымша айырым массивін құрғандықтан, бізде сызықтық кеңістік күрделілігі бар.