查找k個長度的最大平均子數組


難度級別 容易獎學金
經常問 亞馬遜
排列

問題陳述

給你一個 排列 整數和數字k。 問題陳述要求找到k個長度的最大平均子數組。 子數組不過是由原始數組元素的連續塊組成的數組

arr[] = {1,3,12,34,76,10}
[2, 4]

說明:從索引2到索引4的數組保留最大平均值。 因此,[2,4]是長度為2的最大平均子數組。

arr[] = {1,-2,8,3,-6,9}
[1, 3]

說明:從索引1到索引3的數組保留最大平均值。

 

查找k個長度的最大平均子數組的算法

1. Declare a currentSum.
2. Set the currentSum to arr[0].
3. Traverse the array from i=1 to less than the length of n.
  Store and update the addition of currentSum and arr[i] into the currentSum.
4. Set maximumSum to currentSum.
5. Set END to k-1.
6. Traverse the array from i=k to k to i < n.
7. Set sum to sum + arr[i] - arr[i - k].
  Check if the sum is greater than maximumSum.
    1. Set sum to maximumSum.
    2. Set END to i.
8. Return END – k + 1.

 

解釋

給我們一個整數數組和一個數字k。 我們必須找出大小為k的子數組的最大平均值。 這意味著我們發現的平均值應該是數組的k個連續數。 因此,我們將在子數組中找到k個數的平均值。 我們已經聲明了條件,如果 k 大於 n,。 如果為true,則返回-1。 這意味著如果k的值大於n的值,這意味著我們沒有有效的k值,則k不可能大於數組的大小。

我們已經創建了 當前總和。 將給定數組的第一個值複製到currentSum。 然後,因為我們已經對currentSum的值執行了操作,所以將從索引1開始遍歷該數組。 因此,我們將遍歷數組,並獲得currentSum和arr [i]的前一個元素的和,並將其存儲到currentSum中。

我們已經設定了 最大和 到currentSum的第(k-1)個位置,END到k-1。 從第k個位置開始遍歷數組,直到數組的最後一個元素。 我們將有所作為 arr [i]arr [i – k] 並將其添加到sum的值並將其存儲到sum,並且我們也不必擔心我們從位置k開始的負值,因此在其中不會有任何差異。 如果總和大於maximumSum,則將總和和最終值之間的maximumSum設置為i。 我們將重複相同的過程,直到達到數組的長度。 然後我們將返回 結束– k + 1.

該技術也稱為滑動窗口技術。

查找k個長度的最大平均子數組

 

查找k個長度的最大平均子數組的代碼

C ++代碼

#include<iostream>
using namespace std;
int getMaxAvgSubArray(int arr[], int n, int k)
{
    if (k > n)
        return -1;
    int currentSum;
    currentSum = arr[0];
    for (int i = 1; i < n; i++)
        currentSum = currentSum + arr[i];
    int maximumSum = currentSum;
    int END = k - 1;
    for (int i = k; i < n; i++)
    {
        currentSum = currentSum + arr[i] - arr[i-k];
        if (currentSum > maximumSum)
        {
            maximumSum = currentSum;
            END = i;
        }
    }
    return END - k + 1;
}
int main()
{
    int arr[] = {1,3,12,34,76,10};
    int k = 3;
    int n = sizeof(arr)/sizeof(arr[0]);
    int start=getMaxAvgSubArray(arr, n, k);
    cout<<"Maximum average subarray: ["<< start<<" "<< (start + k - 1)<<"]";
    return 0;
}
Maximum average subarray: [2 4]

Java代碼

class MaximumAverageSubarray
{
    public static int getMaxAvgSubArray(int []arr,int n, int k)
    {
        if (k > n)
            return -1;

        int currentSum = arr[0];

        for (int i = 1; i < k; i++)
            currentSum = currentSum + arr[i];

        int maximumSum = currentSum;
        int END = k - 1;

        for (int i = k; i < n; i++)
        {
            currentSum = currentSum + arr[i] - arr[i-k];

            if (currentSum > maximumSum)
            {
                maximumSum = currentSum;
                END = i;
            }
        }
        return END - k + 1;
    }
    public static void main (String[] args)
    {
        int []arr = {1,3,12,34,76,10};
        int k = 3;
        int n = arr.length;
        int start=getMaxAvgSubArray(arr, n, k);
        System.out.println("Maximum average subarray: ["+start+" "+ (start + k - 1)+"]");
    }
}
Maximum average subarray: [2 4]

複雜度分析

時間複雜度以找到k個長度的最大平均子數組

由於我們已經遍歷了數組一次,所以我們具有線性時間複雜度。 O(N) 哪裡 “ n” 是數組中元素的數量。

空間複雜度以找到k個長度的最大平均子數組

由於我們使用數組來存儲輸入,因此我們具有線性的空間複雜度。 O(N) 哪裡 “ n” 是數組中元素的數量。