數組範圍的平均值  


難度級別 中烘焙
經常問 Cadence印度 Expedia的 免費收費 灰色橙色 Roblox Snapchat Snapdeal 時代互聯網 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、XNUMX、XNUMX的平均值是XNUMX

(0,2)因此2,5,1、2、XNUMX、XNUMX的平均值是XNUMX

(4,5)因此7,8、7、XNUMX、XNUMX的平均值是XNUMX

數組範圍的平均值

 

算法  

  1. 創建一個數組PreMeanSum並將其第一個值初始化為給定數組的值。
  2. 從1開始遍歷數組,並將PreMeanSum的先前值與給定數組的當前值之和存儲到PreMeanSum數組的當前值中。
  3. 獲取查詢的左右位置,並檢查給定的左邊位置是否為0,如果為true,則返回PreMeanSum [right] / right + 1的商。
  4. 否則返回PreMeanSum [right] -PreMeanSum [left – 1] / right – left +1的值。

解釋

我們給出了一個整數數組和q個查詢。 因此,我們要求返回給定範圍內數字均值的下限值。 因此,可以像每個查詢一樣遵循一種簡單的方法,從範圍的起點到範圍的終點遍歷數組。 並將所有值的總和存儲為特定值。 假設是否必須找到(0,i)的均值。 因此,對於arr [i],我們將必須對數組零(從一個到給定的ith值)中的所有值求和。 然後,我們將返回該總和與總和(即總和)的商。

也可以看看
下一個更高的頻率元素

但是這樣做的一個缺點是,如果我們有n個查詢,則必須遍歷每個查詢的給定範圍。 它將遍歷n個時間,但是我們使用它的方法將在構建數組一次之後的固定時間內返回每個查詢的答案。

我們將構建數組,為此我們已經聲明了數組PreMeanSum數組。 然後將PreMeanSum數組的第一個元素初始化為給定數組的第一個值。 我們將數組從一個遍歷到數組的長度,這樣做的目的是我們必須在遍歷時將兩個相鄰值的和存儲到當前值。 這就是為什麼我們複製第一個值並從1開始的原因。我們將收到範圍作為起點和終點。 之後,我們將檢查給定的left值是否等於0,如果為true,則返回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

複雜度分析  

時間複雜度

O(n + q) 哪裡 “Q” 是要執行的查詢數量,可以計算為 O(1) 時間複雜度。 O(N) 需要時間來預先計算PreMeanSum。

也可以看看
在排序的旋轉數組中搜索

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。