Среднее значение диапазона в массиве


Сложный уровень средний
Часто спрашивают в Cadence Индия Expedia Свободный заряд СерыйОранжевый Roblox Snapchat Snapdeal Таймс Интернет Яндекс
массив Проблема с запросом

Постановка задачи

В задаче «Среднее значение диапазона в массиве» указано, что вам дается целое массив и 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], нам нужно будет суммировать все значения от нулевого массива, от единицы до данного i-го значения. Затем мы вернем частное этой суммы и общего количества значений, из которых складывается сумма.

Но одним из недостатков этого является то, что мы должны проходить по заданному диапазону для каждого запроса, если у нас есть n запросов. Он будет проходить n количество раз, но подход, который мы используем, вернет ответ на каждый запрос за постоянное время после того, как мы построим массив один раз.

Мы будем строить массив, для этого мы объявили массив PreMeanSum массивом. Затем инициализируйте первый элемент массива PreMeanSum как первое значение данного массива. Мы будем обходить массив от единицы до длины массива, цель этого - мы должны сохранить сумму двух смежных значений с текущим значением во время обхода. Вот почему мы скопировали это первое значение, начиная с 1. Мы получим диапазон как начальную и конечную точки. После этого мы проверим, равно ли данное левое значение 0, если оно истинно, то вернем деление PreMeanSum [right] / right + 1, просто сумма / общее количество значений. В противном случае мы вернем деление разницы PreMeanSum [right] -PreMeanSum [left-1] и right-left + 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

Анализ сложности

Сложность времени

О (п + д) в котором "Q" количество запросов, которые должны быть выполнены, так как среднее значение может быть вычислено в O (1) сложность времени О (п) время требуется для предварительного вычисления PreMeanSum.

Космическая сложность

О (п) в котором «Н» это количество элементов в массиве.