Пронајдете ја под-низата со најмалку просек


Ниво на тешкотија Лесно
Често прашувано во Амазон капитал Еден Лаборатории за месечина
Низа Математика

Изјава за проблем

Дадовте цел ред и број k. Изјавата за проблемот бара да се најде под-низата со најмалку просек, а тоа е да се открие под-низата k елементи, што има минимален просек.

пример

arr[] = {12, 34, 20, 30, 24, 45}
k = 3
Sub-Array of [0, 2] has a minimum average.

Објаснување: 12, 34 и 20 ќе бидат под-низа со големина k, која има најмал просек меѓу сите можни под-низи.

arr[] = {42, 20, 15, 26, 10, 33}
k = 3
Sub-Array of [2, 4] has a minimum average.

Објаснување: 15, 26 и 10 ќе бидат под-низа со големина k, која има најмал просек меѓу сите можни под-низи.

Алгоритам за наоѓање на под-низата со најмалку просек

1. Set start and sum to 0.
2. Traverse the array up to the k, and keep storing the sum of all array elements into the sum.
3. Set leastSum to sum.
4. Traverse the array starting from i=k till i<n.
    1. Get the addition of arr[i] - arr[i-k] and update the value of sum and update it into the sum.
    2. Check if the sum is less than leastSum, if true then update the leastSum to sum and set update start to i-k+1.
5. Print start and start+k-1.

Објаснување

Пронајдете ја под-низата со најмалку просек

Имаме низа на цели броеви и број k. Нашата задача е да го откриеме минималниот просек меѓу сите можни под-низи со големина k. Имаме состојба таму ако n е помал од k, тоа значи ако ја поминеме големината на под-низите од кои треба да го најдеме минималниот просек. Таа низа е поголема од големината на целата низа, тогаш не е можно да се најде тој просек на под-низата. По поставувањето на вредноста на збирот и започнете со 0. beе ја прелистуваме низата и за првото поминување до вредноста на k. Beе го собереме секој елемент од низата и ќе додадеме збир, а потоа ќе го ажурираме. Некоја вредност ќе биде збир по целосното пресекување, а тоа е збир на сите вредности присутни во под-низа.

Следното нешто што ќе направиме е копирање на вредноста на збирот на minimumSum, бидејќи ќе го најдеме минималниот просек меѓу сите под-низи со големина k. Прво ќе ја пресечеме низата од почеток до првите k елементи и ќе ја зачуваме збирот во најмала сума. После тоа, ќе додадеме arr [i] - arr [ik] на најмалку збир за секое i. Само што имаме две вредности, сега бараме трета и проверуваме најмалку. Тогаш, она за што ќе провериме е дали minimumSum е помало од k, ако е точно, тогаш ќе ја ажурираме вредноста на minimumSum и исто така и вредноста на start до i-k + 1. Оваа равенка на ажурирање е само затоа што да се задржи излезот како индексирање на низата нормално затоа што започнавме со k, така што ќе треба да го прилагодиме.

После пресекот, имаме вредност на почеток, но ја немаме крајната вредност на под-низата што има минимален просек, ние само ќе ставиме почеток + k-1, ова ќе помогне да се открие индексот на крај на под-низа.

Код за да се најде под-низата со најмалку просек

C ++ код

#include<iostream>

using namespace std;

void getMinimumAvgSubarray(int arr[], int n, int k)
{
    if (n < k)
        return;

    int start = 0;

    int sum = 0;
    for (int i = 0; i < k; i++)
        sum += arr[i];

    int leastSum = sum;

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

        if (sum < leastSum)
        {
            leastSum = sum;
            start = (i - k + 1);
        }
    }
    cout << "Sub-array between [" << start << ", "<< start + k - 1 << "] has minimum average";
}
int main()
{
    int arr[] = {12, 34, 20, 30, 24, 45};
    int k = 3;
    int n = sizeof arr / sizeof arr[0];
    getMinimumAvgSubarray(arr, n, k);
    return 0;
}
Sub-array between [0, 2] has minimum average

Java код

class MinimumAverageSubArray
{
    public static void getMinimumAvgSubarray(int arr[], int n, int k)
    {
        if (n < k)
            return;

        int start = 0;

        int sum = 0;
        for (int i = 0; i < k; i++)
            sum += arr[i];

        int leastSum = sum;

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

            if (sum < leastSum)
            {
                leastSum = sum;
                start = (i - k + 1);
            }
        }
        System.out.println("Subarray between [" +start + ", " + (start + k - 1) +"] has minimum average");
    }
    public static void main(String[] args)
    {
        int arr[] = {12, 34, 20, 30, 24, 45};
        int k = 3;
        getMinimumAvgSubarray(arr, arr.length, k);
    }
}
Subarray between [0, 2] has minimum average

 

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

Временска комплексност  да се најде под-низата со најмалку просек

Тој) каде „Н“ е бројот на елементи во низата. Тука само што еднаш преминавме низ низата, со тоа алгоритмот има линеарна временска сложеност.

Комплексноста на просторот да се најде под-низата со најмалку просек

Тој) затоа што користевме низа за зачувување на влезот, но решението користи само постојан дополнителен простор.