ንዑስ መስመሩን ቢያንስ በአማካኝ ይፈልጉ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን አቢይ አንድ የሞንፎርግ ቤተ ሙከራዎች
ሰልፍ ሒሳብ

የችግሩ መግለጫ

ኢንቲጀር ድርድር እና ቁጥር k ሰጥተዋል። የችግሩ መግለጫ አነስተኛውን አማካይ ንዑስ ክፍልን ለማግኘት ይጠይቃል ፣ ይህም አነስተኛ አማካይ አማካይ የ k አባሎችን ንዑስ-ድርድር ለማወቅ ነው ፡፡

ለምሳሌ

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

ማብራሪያ: - 12 ፣ 34 እና 20 ሁሉም ሊሆኑ ከሚችሉ ንዑስ-አሰራሮች መካከል ቢያንስ አማካይ አማካይ የሆነ የክብ ንዑስ ክፍል ይሆናል ፡፡

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

ማብራሪያ: - 15 ፣ 26 እና 10 ሁሉም ሊሆኑ ከሚችሉ ንዑስ-አሰራሮች መካከል ቢያንስ አማካይ አማካይ የሆነ የክብ ንዑስ ክፍል ይሆናል ፡፡

ንዑስ ስርዓቱን ቢያንስ በአማካይ ለማግኘት አልጎሪዝም

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. የእኛ ተግባር በሁሉም ሊሆኑ ከሚችሉ ንዑስ-ስብስቦች መካከል አነስተኛውን አማካይ ማወቅ ነው ፡፡ N ከ k በታች ከሆነ እዛው ውስጥ ያለንበት ሁኔታ አለብን ፣ ይህ ማለት አነስተኛውን አማካይ ለማግኘት የሚያስፈልገንን ንዑስ-ድርድሮች መጠን ካለፍን ማለት ነው ፡፡ ያ ድርድር ከጠቅላላው ድርድር መጠን ይበልጣል ፣ ከዚያ ያንን ንዑስ-ድርድር አማካይ ማግኘት አይቻልም። የድምር ዋጋን ካቀናበሩ በኋላ ወደ 0. ከጀመርን በኋላ ድርድርን እና ለመጀመሪያው የትራንስፖርት ጉዞ እስከ ኪ ዋጋ ድረስ እናልፋለን ፡፡ የአንድ ድርድርን እያንዳንዱን ንጥረ ነገር አንስተን ወደ ድምርው እንጨምራለን ፣ ከዚያ እናዘምነው። የተወሰነ እሴት ሙሉ በሙሉ ከተጓዘ በኋላ ድምር ይሆናል ፣ ያ ደግሞ በንዑስ ድርድር ውስጥ የሚገኙ ሁሉም እሴቶች ድምር ነው።

ቀጣዩ የምንሰራው ነገር ቢኖር የሁሉም ንዑስ-ክፍል መጠን ዝቅተኛውን አማካይ እናገኛለንና ፣ ምክንያቱም ቢያንስ ለሱም የመደመር ዋጋን መቅዳት ነው። መጀመሪያ ድርድርን ከመጀመሪያው እስከ መጀመሪያው k ንጥረ ነገሮች ድረስ እናልፋለን እና ድምርውን በትንሹ በሱም ውስጥ እናከማቸዋለን ፡፡ ከዚያ በኋላ arr [i] - arr [ik] ን ቢያንስ iSum ወደ እያንዳንዱ i እንጨምራለን ፡፡ ይህ እኛ አሁን ሁለት እሴቶች አሉን ሦስተኛውን እየፈለግን እና ቢያንስ እያጣራን ነው ፡፡ ከዚያ የምንፈትሽበት ነገር ቢኖር ቢያንስ ሱም ከ k ያነሰ ከሆነ እውነት ከሆነ የትንሽ ሱምን ዋጋ እና እንዲሁም የመነሻ እሴትን ወደ i-k + 1 እናዘምነዋለን ፡፡ ይህ የዝማኔ ቀመር በኪው ስለጀመርን ውጤቱን እንደ አንድ የድርድር ማውጫ ማውጫ መደበኛ አድርጎ ለማቆየት ብቻ ስለሆነ ማስተካከል ያስፈልገናል።

ከተሻገረን በኋላ የመነሻ ዋጋ አለን ግን ዝቅተኛ አማካይ ንዑስ-ድርድር የማጠናቀቂያ ዋጋ የለንም ፣ ጅምር + k-1 ን ብቻ እናደርጋለን ፣ ይህ የ ንዑስ-ድርድር

ንዑስ ቡድኑን ቢያንስ በአማካይ ለማግኘት ኮድ

ሲ ++ ኮድ

#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

የጃቫ ኮድ

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

 

ውስብስብነት ትንተና

የጊዜ ውስብስብነት  ንዑስ ቡድኑን ቢያንስ በአማካኝ ለማግኘት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። እዚህ አንድ ጊዜ በድርድሩ ላይ ተሻግረናል ፣ ስለሆነም አልጎሪዝም የመስመር ጊዜ ውስብስብነት አለው።

የቦታ ውስብስብነት ንዑስ ቡድኑን ቢያንስ በአማካኝ ለማግኘት

ሆይ (n) ምክንያቱም ግብዓቱን ለማከማቸት አንድ ድርድር እንጠቀም ነበር ነገር ግን መፍትሄው የማያቋርጥ ተጨማሪ ቦታን ብቻ ይጠቀማል ፡፡