Ялгааны массив | 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 утгыг нэмж, бүтээсэн массивын баруун индексээс 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 дахь хэрэгжилт

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" нь массив дахь элементүүдийн тоо юм. Бид нэмэлт ялгааны массивыг бий болгосон тул шугаман орон зайн нарийн төвөгтэй байдалтай болно.