Сярэдняе значэнне дыяпазону ў масіве


Узровень складанасці серада
Часта пытаюцца ў Cadence Індыя Expedia FreeCharge Шэры Аранжавы Roblox Snapchat Snapdeal Times Інтэрнэт Яндэкс
масіў Задача запыту

Пастаноўка праблемы

Праблема "Сярэдняе значэнне дыяпазону ў масіве" абвяшчае, што вам дадзена цэлае масіў і 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.

Тлумачэнне

Мы прывялі цэлы масіў і колькасць запытаў. Такім чынам, мы папрасілі вярнуць мінімальнае значэнне сярэдняга з лікаў, якія ўваходзяць у зададзены дыяпазон. Такім чынам, простым падыходам, якога можна прытрымлівацца, як і для кожнага запыту, мы будзем перамяшчаць масіў ад пачатковай кропкі дыяпазону да канчатковай кропкі дыяпазону. І захоўвайце суму ўсіх значэнняў да пэўнага значэння. Дапусцім, калі нам трэба знайсці сярэдняе (0, i). Такім чынам, arr [i], нам прыйдзецца падсумаваць усе значэнні ад нулявога масіва, адзін да дадзенага i-га значэння. Тады мы вернем каэфіцыент гэтай сумы і агульную колькасць значэнняў, з якіх складаецца сума.

Але адзін недахоп гэтага заключаецца ў тым, што пры кожным запыце нам трэба прайсціся па зададзеным дыяпазоне, калі ў нас ёсць 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" - колькасць запытаў, якія трэба выканаць, паколькі сярэдняе значэнне можна вылічыць у O (1) складанасць часу. Аб (п) для папярэдняга вылічэння PreMeanSum патрабуецца час.

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве.