სხვაობა მასივი | დიაპაზონის განახლების მოთხოვნა O- ში (1)  


Რთული ტური Hard
ხშირად ეკითხებიან არსიუმი 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)Pin

 

სხვაობის მასივის ალგორითმი  

  1. შექმენით იმავე ზომის მასივი, როგორც მოცემული მასივი.
  2. პირველი ინდექსის შედგენა მოცემულია მასივის პირველი ელემენტის მიხედვით, ხოლო ბოლო ინდექსი 0.-ით და ყველა სხვა ინდექსები ივსება მიმდინარე და წინა ელემენტის სხვაობით.
  3. განახლების ყოველი მოთხოვნისთვის, დაამატეთ X მნიშვნელობა მასივის მოცემულ მარცხენა ინდექსში და X ჩამოაცილეთ შექმნილი მასივის მარჯვენა ინდექსიდან.
  4. ბეჭდვის ყველა მოთხოვნისთვის, პირველ რიგში, ჩვენ შეავსებთ შეყვანის მასივს ფორმულის გამოყენებით A [i] = D [i] + A [i-1]. შემდეგ დაბეჭდეთ მნიშვნელობები.
იხილეთ ასევე
ორი დალაგებული მასივის გათვალისწინებით იპოვნეთ ყველა წყვილი, რომელთა ჯამია x

განმარტება  

მოცემულია მასივი და რიცხვი და ორი ტიპის მოთხოვნა. ასე რომ, ჩვენ უნდა შევასრულოთ ორი ტიპის მოთხოვნა. ჩვენ გვექნება ორი რიცხვი, რომლებიც წარმოადგენს დიაპაზონს 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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. მას შემდეგ, რაც შევქმენით დამატებითი განსხვავების მასივი, ჩვენ გვაქვს ხაზოვანი სივრცის სირთულე.