Орташа минимумды табыңыз  


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Capital One Moonfrog зертханалары
Array математика

Проблемалық мәлімдеме  

Сіз бүтін массив пен 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-ден кіші болса, онда біз ең төменгі орташа мәнді табуымыз керек ішкі массивтің өлшемін берсек дегенді білдіреді. Бұл жиым бүкіл массивтің өлшемінен үлкен, сондықтан бұл ішкі жиымның орташа мәнін табу мүмкін емес. Қосындының мәнін орнатқаннан кейін 0-ден бастаймыз. Біз массивті және k-тің мәніне дейін бірінші өтпелі жүреміз. Біз массивтің әр элементін жинап, қосындысын қосамыз, содан кейін оны жаңартамыз. Толық өтуден кейін кейбір мәндер қосындыда болады, және бұл ішкі жиымдағы барлық мәндердің қосындысы.

Сондай-ақ, қараңыз
Берілген қосындымен жұпты санау

Келесі біз қосындының мәнін minimumSum-ға көшіруді қолға аламыз, өйткені k өлшемінің барлық ішкі жиымының ішінен минималды орташа мәнді табамыз. Алдымен біз массивті басынан бастап k элементіне дейін айналып өтіп, қосындыны ең азSum-да сақтаймыз. Осыдан кейін біз әр i үшін ең аз Sum-ге arr [i] - arr [ik] қосамыз. Бұл бізде екі мән бар, енді біз үшінші мәнді іздейміз, ал кем дегенде тексереміз. Сонда біз тексеретініміз: егер егер бұл ең аз болса, егер ол кем болса, егер ол шын болса, онда біз ең аз Sum мәнін және 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

 

Сондай-ақ, қараңыз
Жиымдағы қайталанбайтын элементтердің (ерекше) қосындысын табыңыз

Күрделілікті талдау  

Уақыттың күрделілігі  ішкі ортаны минимум орташадан табу

O (N) қайда «N» - бұл массивтегі элементтер саны. Бұл жерде біз массивтің үстінен бір рет өттік, сондықтан алгоритм уақыттың сызықтық күрделілігіне ие.

Ғарыштың күрделілігі ішкі ортаны минимум орташадан табу

O (N) өйткені біз кірісті сақтау үшін массив қолдандық, бірақ шешім тек тұрақты қосымша орынды пайдаланады.