დიაპაზონის საშუალო მასივი


Რთული ტური საშუალო
ხშირად ეკითხებიან კადენს ინდოეთი Expedia უფასო დატენვა რუხი ნარინჯისფერი რობლოქსი Snapchat Snapdeal Times ინტერნეტი Yandex
Array შეკითხვის პრობლემა

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

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

მაგალითი

array[] = {2, 5, 1, 6, 7, 8}

Query: {(1, 4), (0,2), (4,5)}
4 2 7

განმარტება

(1,4), ასე რომ, საშუალო მნიშვნელობა 5,1,6,7, რომელიც არის 4

(0,2), ასე რომ, საშუალო მნიშვნელობა 2,5,1, რომელიც არის 2

(4,5), ასე რომ, საშუალო მნიშვნელობა 7,8, რომელიც არის 7

დიაპაზონის საშუალო მასივი

 

ალგორითმი

  1. შექმენით მასივი PreMeanSum და წამოიწყეთ მისი პირველი მნიშვნელობა მოცემული მასივის მნიშვნელობად.
  2. გაიარეთ მასივი 1-დან და შეინახეთ PreMeanSum- ის წინა მნიშვნელობის ჯამი და მოცემული მასივის მიმდინარე მნიშვნელობა PreMeanSum მასივის მიმდინარე ღირებულებაში.
  3. მიიღეთ მოთხოვნის მარცხენა და მარჯვენა პოზიცია და შეამოწმეთ არის მოცემული მარცხენა პოზიცია 0, თუ სიმართლეა, შემდეგ დაუბრუნეთ PreMeanSum [მარჯვნივ] / მარჯვნივ + 1-ის კოეფიციენტი.
  4. სხვა შემთხვევაში დააბრუნეთ PreMeanSum- ის მნიშვნელობა [მარჯვნივ] -PreMeanSum [მარცხნივ - 1] / მარჯვნივ - მარცხნივ +1.

განმარტება

ჩვენ მივეცით მთლიანი მასივი და q მოთხოვნების რაოდენობა. ამრიგად, ჩვენ ვთხოვეთ დავაბრუნოთ მოცემული დიაპაზონის რიცხვის საშუალო მნიშვნელობის იატაკის მნიშვნელობა. ამრიგად, მარტივი მიდგომა, რომელიც შეიძლება დაიცვას, როგორც თითოეული მოთხოვნისთვის, მასივს გადავხედავთ დიაპაზონის საწყისი წერტილიდან დიაპაზონის დასასრულ წერტილამდე. და შეინახეთ ყველა მნიშვნელობის ჯამი კონკრეტულ მნიშვნელობამდე. დავუშვათ, თუ უნდა ვიპოვნოთ (0, i) - ის საშუალო. ამ arr [i] - ზე, ჩვენ მოგვიწევს ყველა მნიშვნელობის ჯამი ნულოვანი მასივიდან, ერთი მოცემული ლის მნიშვნელობამდე. შემდეგ ჩვენ დავაბრუნებთ ამ ჯამის კოეფიციენტს და მნიშვნელობების საერთო რაოდენობას, რომელთა ჯამიც გაკეთებულია.

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

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

კოდი

C ++ კოდი მასივში დიაპაზონის საშუალო მნიშვნელობის მოსაძებნად

#include<iostream>
#include<math.h>

#define MAX 1000005
using namespace std;

int PreMeanSum[MAX];

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

int getMeanInRange(int l, int r)
{
    if (l == 0)
        return floor(PreMeanSum[r] / (r + 1));

    return floor( (PreMeanSum[r] - PreMeanSum[l - 1]) / (r - l + 1));
}

int main()
{

    int arr[] = {2,5,1,6,7,8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    buildPreMean(arr, n);
    cout << getMeanInRange(1, 4) << endl;
    cout << getMeanInRange(0, 2) << endl;
    cout << getMeanInRange(4, 5) << endl;
    return 0;
}
4
2
7

ჯავის კოდი მასივში დიაპაზონის საშუალო მნიშვნელობის მოსაძებნად

class MeanInRange
{
    public static final int MAX = 1000005;

    static int PreMeanSum[] = new int[MAX];

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

    static int getMeanInRange(int l, int r)
    {
        if (l == 0)
            return (int)Math.floor(PreMeanSum[r] / (r + 1));

        return (int)Math.floor((PreMeanSum[r] -
                                PreMeanSum[l - 1]) / (r - l + 1));
    }

    public static void main(String[] args)
    {
        int arr[] = {2,5,1,6,7,8 };
        int n = arr.length;
        buildPreMean(arr, n);
        System.out.println(getMeanInRange(1, 4));
        System.out.println(getMeanInRange(0, 2));
        System.out.println(getMeanInRange(4, 5));
    }
}
4
2
7

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

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

O (n + q) სადაც "Q" არის შეკითხვების რაოდენობა, რომელიც უნდა შესრულდეს, რადგან საშუალო გამოითვლება O (1) დროის სირთულე. O (n) დრო სჭირდება PreMeanSum- ის წინასწარ გამოთვლას.

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

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