Миёнаи диапазон дар массив  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Cadence Ҳиндустон Expedia FreeCharge Грей норанҷӣ Roblox Snapchat Snapdeal Интернет Times 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 [right] / right + 1 -ро баргардонед.
  4. Дигар арзиши PreMeanSum [right] -PreMeanSum [left - 1] / right - left +1 -ро бармегардонад.

Шарҳ

Мо массиви бутун ва шумораи q саволҳоро додем. Ҳамин тавр, мо хоҳиш кардем, ки арзиши фарши миёнаи рақамҳои дар диапазони додашуда баргардонида шавад. Ҳамин тариқ, усули оддие, ки барои ҳар як пурсиш пайравӣ кардан мумкин аст, мо массивро аз нуқтаи ибтидои диапазон то нуқтаи интиҳои диапазон мегузарем. Ва ҷамъи ҳамаи арзишҳоро ба арзиши муайян нигоҳ доред. Фарз мекунем, ки агар мо маънои миёнаи (0, i) -ро ёбем. Ҳамин тавр, arr [i], мо бояд ҳамаи арзишҳоро аз массиви сифр, як то арзиши ith додашуда ҷамъбаст кунем. Он гоҳ мо миқдори он суммаро ва шумораи умумии қиматҳоро, ки аз он ҳосил шудааст, бармегардонем.

ҳамчунин нигаред
Элементи навбатии бузургтар

Аммо як камбудие, ки дар он аст, мо бояд барои ҳар як пурсиш доираи диапазони додашударо тай кунем, агар n савол дошта бошем. Он n ​​миқдори вақтро тай хоҳад кард, аммо равише, ки мо онро истифода мебарем, пас аз сохтани массив, ҷавоби ҳар як дархостро дар вақти доимӣ бармегардонад.

Мо массивро месозем, зеро барои он массиви PreMeanSum эълон кардем. Пас унсури якуми массиви PreMeanSum -ро ҳамчун арзиши якуми массиви додашуда оғоз намоед. Мо массивро аз як то дарозии массив тай хоҳем кард, ҳадафи иҷрои он мо бояд ҳаҷми ду қимати ҳамшафатро ба арзиши ҷорӣ ҳангоми гардиш нигоҳ дорем. Аз ин рӯ, мо ин арзиши аввалро нусхабардорӣ кардем ва аз 1 сар карда, диапазонро ҳамчун нуқтаи оғоз ва нуқтаи хотима мегирем. Пас аз он, мо месанҷем, ки арзиши чапи додашуда ба 0 баробар аст, агар рост бошад, пас тақсимоти PreMeanSum [right] / right + 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) мураккабии вақт. Эй (н) барои ҳисоб кардани PreMeanSum вақт лозим аст.

ҳамчунин нигаред
Ҷустуҷӯ дар массиви мураттабшуда

Мураккабии фазо

Эй (н) ки дар "Н" шумораи унсурҳои массив аст.