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


Რთული ტური Easy
ხშირად ეკითხებიან BlackRock GE Healthcare Moonfrog ლაბორატორიები ანოტაცია ტაქსი 4 Twilio
Array ლარსენი და ტუბრო შეკითხვის პრობლემა

პრობლემის განცხადება

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

მაგალითი

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

განმარტება

ყველა რიცხვის ჯამი დიაპაზონს შორის (0, 4) არის 40 და ყველა რიცხვის ჯამი დიაპაზონს შორის (1, 3) 24 არის.

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

 

ალგორითმი

  1. შექმნა მასივის ჯამიArray ზომის იგივეა, რაც მოცემული მასივი.
  2. გაიარეთ მოცემული მასივი და შეინახეთ sumArray- ის წინა ელემენტისა და მოცემული მასივის მიმდინარე ელემენტის ჯამი და შეინახეთ sumArray- ში.
  3. თითოეული მოთხოვნისთვის, თუ მარცხენა ტოლია 0, მაშინ დააბრუნე sumArray [მარჯვნივ],
  4. სხვას დაუბრუნეთ sumArray [მარჯვნივ] - sumArray [მარცხნივ - 1].

განმარტება

ჩვენ მივეცით მთელი რიგის მთელი რიგი და დიაპაზონი, მოგვთხოვეს გაეცნოთ მოცემული დიაპაზონის ყველა ელემენტის ჯამს თითოეული მოთხოვნისთვის. თითოეული მოთხოვნა შედგება დიაპაზონისგან, როგორც დიაპაზონის საწყისი და დამთავრებული წერტილი. ეს კითხვა არ შეიცავს განახლების მოთხოვნას. ეს ნიშნავს, რომ მოთხოვნის პასუხის გაცემის დროს არ არის საჭირო რაიმე საკითხის განახლება. ჩვენ უბრალოდ ავაშენებთ მოცემულ მასივს ისე, რომ ყველა ინდექსში 0 ელემენტიდან მიმდინარე ინდექსამდე ყველა ელემენტის ჯამი იყოს აგებული მასივის ith პოზიციაზე. ამ გზით, ყველა მოთხოვნა გადაჭრილდება O (1), O (n) დამატებითი ადგილით.

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

როდესაც მივიღებთ მოთხოვნას, რომელიც შედგება ნებისმიერი დიაპაზონისგან, და თუ აღმოვაჩინეთ, რომ დიაპაზონის მარცხენა ან საწყისი წერტილი 0-ის ტოლია, ჩვენ დაუბრუნებთ sumArray- ის მნიშვნელობას [მარჯვნივ], რაც ზემოთ განვიხილეთ, არის თუ არა მარცხენა დიაპაზონი 0 – ის ტოლი, ჩვენ დავაბრუნებთ sumArray [მარჯვნივ] და sumArray [მარცხნივ –1] სხვაობას. ამისათვის საჭირო იქნება პასუხები. ეს მიდგომა ასევე ერთ – ერთი ყველაზე მარტივი გზაა, რომლითაც ვიყენებთ დინამიური პროგრამირება.

კოდი

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

#include<iostream>

using namespace std;

void buildSumArray(int arr[], int n, int sumArray[])
{
    sumArray[0] = arr[0];
    for (int i = 1; i < n; i++)
        sumArray[i] = arr[i] + sumArray[i - 1];
}

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

დიაპაზონის ჯამური მოთხოვნების ჯავის კოდი განახლებების გარეშე

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

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

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

O (N + Q),  რადგან ჩვენ გვჭირდება O (N), რომ გამოვთვალოთ sumArray და შემდეგ O (1) დრო თითოეული მოთხოვნისთვის.

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

მოცემულ მიდგომაში ჩვენ შევქმენით ახალი მასივი sumArray ელემენტების ჯამის შესანახად 0 – დან i – მდე. ამრიგად, ეს მიდგომა მოითხოვს O (N) სივრცე მაგრამ შეგვეძლო ორიგინალი მასივის შეცვლაც. მაშინ სივრცის სირთულე დაიკლებოდა მუდმივამდე.