მუდმივი დროის დიაპაზონი დაამატეთ ოპერაცია მასივს


Რთული ტური Easy
ხშირად ეკითხებიან CodeNation დე შოუ დირექტი Expedia Google
Array დინამიური პროგრამირება

თქვენ მიანიჭეთ მთელი რიცხვი მასივი თავდაპირველად, იგი ინიცირებული იყო 0 – ით და ასევე მიეცა დიაპაზონი. ამოცანაა მოცემული რიცხვის დამატება მასივის დიაპაზონში და დაბეჭდილი შედეგიანი მასივი.

მაგალითი

arr[] = {0, 0, 0, 0, 0}

Query: {(0, 2, 50), (3, 4, 20), (1, 3, 30)}
50 80 80 50 20

განმარტება

50 მასივს დაემატება 0 – დან 2 – მდე, მასივი გახდება {50, 50, 50, 0, 0}

20 მასივს დაემატება 3 – დან 4 – მდე, მასივი გახდება {50, 50, 50, 20, 20}

30 მასივს დაემატება 1 – დან 3 – მდე, მასივი გახდება {50, 80, 80, 80, 20}

მუდმივი დროის დიაპაზონი დაამატეთ ოპერაცია მასივს

 

ალგორითმი

  1. დიაპაზონის თითოეული მოთხოვნისთვის მიჰყევით ნაბიჯებს.
    1. მოცემული მნიშვნელობა დაამატეთ მასივის მარცხენა ინდექსში და შეინახეთ იგი თავისთვის.
    2. შეამოწმეთ, არის თუ არა მნიშვნელობის უფლება მასივის ბოლო ინდექსის ტოლი, შემდეგ გამოაკელით მოცემული მნიშვნელობა მასივის მარჯვნივ + 1 პოზიციაზე და შეინახეთ იგი თავისთვის.
  2. მასივის დაბეჭდვამდე მასივი განაახლეთ მასივის მეშვეობით და დაამატეთ წინა და ამჟამინდელი მნიშვნელობა და შეინახეთ მას მასივში.
  3. განახლების შემდეგ, დაბეჭდეთ შედეგიანი მასივი.

მუდმივი დროის დიაპაზონის განმარტება მასივზე ოპერაციის დამატება

მოცემულია მთელი მასივი და დასამატებელი რიცხვი. ჩვენ ასევე მოცემულია შეკითხვის დიაპაზონი. იგი შეიცავს დიაპაზონის საწყისი წერტილს როგორც მარცხნივ და დიაპაზონის დასრულების წერტილს როგორც მარჯვნივ. ჩვენ მოგვთხოვეს მოცემულ დიაპაზონში მოცემული რიცხვის დამატება ყველა შესაძლო მთელი რიცხვისთვის. შემდეგ საბოლოოდ დაბეჭდეთ შედეგიანი მასივი. ამისათვის ჩვენ ვაპირებთ დამატების ოპერაციის შესრულებას ძალიან შეცვლილი გზით. ჩვენ შევავსებთ მასივის ინდექსის მნიშვნელობებს მოცემული მნიშვნელობით მასივის მარცხენა და მარჯვენა + 1 პოზიციაზე და ამ მასივის განახლების დაბეჭდვამდე.

თითოეული მოცემული შეკითხვისთვის, მარცხნივ და მარჯვნივ, ჩვენ ვაძლევთ მოცემულ მნიშვნელობას მარჯვენა მარცხენა ინდექსში, მახსოვს მხოლოდ მარცხენა ინდექსში. და სწორი მნიშვნელობისთვის, ჩვენ ვაპირებთ შეამოწმოთ, არის თუ არა მნიშვნელობის უფლება მასივის ბოლო ინდექსის ტოლი, თუ მოცემული პირობა დაკმაყოფილებულია, ჩვენ ვაპირებთ განაახლოთ მოცემული მნიშვნელობის ინდექსი, გამოვართვით მოცემულ მნიშვნელობას მასივის სწორი ინდექსი და შეინახეთ იგი მასივის სწორი პოზიციის ინდექსში. თითოეული შეკითხვისთვის, ჩვენ ვაპირებთ ამ ოპერაციების შესრულებას.

ახლა ჩვენ უნდა დავბეჭდოთ მასივი, მაგრამ მანამდე, ჩვენ ვაპირებთ განახლების ყველა მნიშვნელობას, დამატებით ოპერაციას, რომელიც ჩვენ შევასრულეთ, ჩვენ უნდა განაახლოთ ეს. ასე რომ, განაახლეთ მასივი, მასივის გავლით და დაამატეთ მოცემული მასივის მიმდინარე მნიშვნელობა და წინა მნიშვნელობა და შეინახეთ მას მასივის ამჟამინდელ მდგომარეობაში. შემდეგ მას შემდეგ, ჩვენ ვაპირებთ მასივის დაბეჭდვას.

კოდი

განხორციელება C ++ - ში მუდმივი დროის დიაპაზონისთვის დაამატეთ ოპერაცია მასივზე

#include<iostream>

using namespace std;

void update(int arr[], int N)
{
    for (int i = 1; i < N; i++)
        arr[i] += arr[i - 1];
}

void addOperation(int arr[], int N, int left, int right, int value)
{
    arr[left] += value;
    if (right != N - 1)
        arr[right + 1] -= value;
}

void printArray(int arr[], int N)
{
    update(arr, N);
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int N = 5;

    int arr[N] = {0};

    addOperation(arr, N, 0, 2, 50);
    addOperation(arr, N, 3, 4, 20);
    addOperation(arr, N, 1, 3, 30);

    printArray(arr, N);
    return 0;
}
50 80 80 50 20

Java- ში განხორციელება მუდმივი დროის დიაპაზონისთვის დაამატეთ ოპერაცია მასივზე

class AddOperation
{
    static void update(int arr[], int N)
    {
        for (int i = 1; i < N; i++)
            arr[i] += arr[i - 1];
    }
    static void addOperation(int arr[], int N, int left, int right, int value)
    {
        arr[left] += value;
        if (right != N - 1)
            arr[right + 1] -= value;
    }
    static void printArray(int arr[], int N)
    {
        update(arr, N);

        for (int i = 0; i < N; i++)
            System.out.print(""+arr[i]+" ");
        System.out.print("\n");
    }
    public static void main (String[] args)
    {
        int N = 5;

        int arr[] = new int[N];

        addOperation(arr, N, 0, 2, 50);
        addOperation(arr, N, 3, 4, 20);
        addOperation(arr, N, 1, 3, 30);
        printArray(arr, N);
    }
}
50 80 80 50 20

სირთულის ანალიზი

დროის სირთულე

O (N + Q) სადაც "N" არის მასივის ელემენტების რაოდენობა და "Q" არის შეკითხვების რაოდენობა. იმიტომ, რომ ჩვენ გავაუმჯობესეთ მნიშვნელობა მარცხენა ინდექსთან და შევამცირეთ მნიშვნელობა +1 ინდექსთან, თუ ის მასივის საზღვარში არსებობს.

სივრცის სირთულე

O (N) სადაც "N" არის მასივის ელემენტების რაოდენობა.