Массив фарқият | Дархости навсозии диапазон дар O (1)  


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Артезий CodeNation Directi Expedia Google Qualcomm
тартиботи ҳарбӣ Масъалаи пурсиш

Ба шумо як ҳамаҷониба асал ва ду намуди дархостҳо, яке илова кардани шумораи додашуда дар диапазон ва дигаре барои чопи тамоми массив. Мушкилоти “Массиви фарқият | Дархости навсозии диапазон дар 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 илова карда шавад. Яке аз усулҳо метавонад истифодаи усули соддалавҳона бошад. Барои ин, массиви додашударо ҳар дафъае, ки мо бояд қиматҳоро нав кунем, гузаред.

Як ҳалли беҳтар дар ин ҷо муҳокима карда мешавад, яъне эҷоди массиви иловагӣ, ки фарқиятро нигоҳ медорад. Барои ҳамин онро массиви фарқият меноманд. Аввалан, унсури якуми массиви фарқро ҳамчун унсури якуми массиви вурудӣ оғоз кунед. Пас унсури охирини массиви фарқро ба 0 таъин кунед. Пас аз он, мо массивро тай намуда, фарқи арзиши ҷорӣ ва арзиши қаблиро дар шохиси ҷорӣ дар массиви фарқ нигоҳ медорем.

Мо арзишҳоро ҳамчун диапазон мегирем, агар дархости навсозӣ пайдо кунем. Дар баробари ин ба мо рақам низ дода мешавад. Пас, мо ин рақамро ба индекси чапи диапазони массиви фарқ илова мекунем. Ба ҳамин монанд, арзиши 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

Татбиқ дар Java барои Array Difference

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" шумораи пурсишҳои чопӣ, ки ҳангоми гирифтани дархости навсозӣ иҷро карда мешавад О (1) вақт.

ҳамчунин нигаред
Subarrays бо унсурҳои гуногун

Мураккабии фазо

Эй (н) ки дар "Н" шумораи унсурҳои массив аст. Азбаски мо массиви иловагии фарқро ба вуҷуд овардем, мо мураккабии фазоии хаттӣ дорем.