Μέσος όρος εύρους σε πίνακα


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις Cadence Ινδία Expedia Χωρίς χρέωση GreyOrange Roblox Snapchat Snapdeal Times Internet Yandex
Παράταξη Πρόβλημα ερωτήματος

Δήλωση προβλήματος

Το πρόβλημα "Μέσος όρος εύρους σε πίνακα" δηλώνει ότι σας δίνεται ένα ακέραιος αριθμός παράταξη και 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], θα πρέπει να αθροίσουμε όλες τις τιμές από τον πίνακα μηδέν, μία έως τη δεδομένη τιμή ith. Στη συνέχεια, θα επιστρέψουμε το πηλίκο αυτού του αθροίσματος και τον συνολικό αριθμό τιμών, από τις οποίες γίνεται το άθροισμα.

Αλλά ένα μειονέκτημα αυτού είναι ότι πρέπει να διασχίσουμε το δεδομένο εύρος για κάθε ερώτημα εάν έχουμε n ερωτήματα. Θα διασχίσει τον αριθμό 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

Κωδικός Java για εύρεση μέσου εύρους σε πίνακα

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" είναι ο αριθμός των ερωτημάτων που θα εκτελεστούν καθώς ο μέσος όρος μπορεί να υπολογιστεί σε Ο (1) χρονική πολυπλοκότητα. O (n) απαιτείται χρόνος για τον υπολογισμό του PreMeanSum.

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.