ઓછામાં ઓછી સરેરાશ સાથે સબઅરેરે શોધો  


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન કેપિટલ વન મૂનફ્રોગ લેબ્સ
અરે મઠ

સમસ્યા નિવેદન  

તમે પૂર્ણાંક એરે આપ્યો છે અને કે. સમસ્યાનું નિવેદન ઓછામાં ઓછું સરેરાશ સાથે સબબ્રે શોધવા માટે કહે છે, જે કે તત્વોની પેટા-એરે શોધવા માટે છે, જેમાં લઘુત્તમ સરેરાશ હોય છે.

ઉદાહરણ  

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.

સમજૂતી

ઓછામાં ઓછી સરેરાશ સાથે સબઅરેરે શોધોપિન

અમારી પાસે છે એરે પૂર્ણાંકો અને સંખ્યા કે. અમારું કાર્ય એ કે.કે.ના તમામ સંભવિત પેટા એરેની વચ્ચે લઘુત્તમ સરેરાશ શોધવાનું છે. આપણી ત્યાં શરત છે જો એન કે કરતા ઓછો હોય, તો તેનો અર્થ એ કે જો આપણે પેટા એરેના કદને પસાર કરીએ જેમાંથી આપણે લઘુત્તમ સરેરાશ શોધવાની જરૂર છે. તે એરે આખા એરેના કદ કરતા વધારે છે, પછી તે પેટા-એરે સરેરાશ શોધવાનું શક્ય નથી. સરવાળાનું મૂલ્ય સેટ કર્યા પછી અને 0 થી શરૂ કરીશું પછી, આપણે K ની કિંમત સુધી એરેને શોધીશું અને પ્રથમ ટ્રversવર્સલ કરીશું. અમે એરેના દરેક તત્વને પસંદ કરીશું અને સરવાળો ઉમેરીશું, પછી તેને અપડેટ કરીશું. સંપૂર્ણ મૂલ્યાંકન પછી કેટલાક મૂલ્યનો સરવાળો થશે, અને તે પેટા-એરેમાં હાજર તમામ મૂલ્યોનો સરવાળો છે.

આ પણ જુઓ
આપેલ રકમ સાથે જોડણી ગણતરી

આગળની વસ્તુ આપણે કરવા જઈ રહ્યા છીએ, સરવાળાનું મૂલ્ય ઓછામાં ઓછી સુમની નકલ કરી રહ્યું છે, કારણ કે આપણે કદના બધા પેટા-એરેમાં લઘુતમ સરેરાશ શોધીશું. આપણે પ્રથમ એરે પ્રારંભથી પહેલા કે તત્વો સુધી પસાર કરીશું, અને સરવાળો ઓછામાં ઓછામાં સંગ્રહિત કરીશું. પછીથી આપણે દરેક i માટે arr [i] - arr [ik] માં ઓછામાં ઓછા સુમ ઉમેરીશું. આ ફક્ત અમારી પાસે બે મૂલ્યો છે હવે આપણે ત્રીજા માટે શોધી રહ્યા છીએ અને ઓછામાં ઓછા તપાસીએ છીએ. તો પછી આપણે જો તપાસ કરીશું કે જો ઓછામાં ઓછી સુ કે કરતાં ઓછી હોય, જો તે સાચું છે, તો આપણે લઘુત્તમ સુમનું મૂલ્ય અને શરુઆતની કિંમત પણ આઈ-કે + + 1 કરીશું. અપડેટનું આ સમીકરણ ફક્ત એરેના અનુક્રમણિકા તરીકે આઉટપુટ રાખવા માટે છે કારણ કે આપણે કે સાથે શરૂ કર્યું છે, તેથી આપણે તેને સમાયોજિત કરવાની જરૂર રહેશે.

આ આડઅસર પછી, આપણી પાસે પ્રારંભનું મૂલ્ય છે, પરંતુ અમારી પાસે પેટા-એરેનું અંતિમ મૂલ્ય નથી જેનું લઘુત્તમ સરેરાશ છે, આપણે ફક્ત શરૂઆત + કે -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

 

આ પણ જુઓ
એરેમાં પુનરાવર્તિત તત્વો (વિશિષ્ટ) તત્વોનો સરવાળો શોધો

જટિલતા વિશ્લેષણ  

સમય જટિલતા  ઓછામાં ઓછી સરેરાશ સાથે સબબ્રે શોધવા માટે

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. અહીં આપણે એક વાર માત્ર એરે ઉપરથી પસાર થઈ ગયા છીએ, આમ તો અલ્ગોરિધમમાં રેખીય સમયની જટિલતા હોય છે.

અવકાશ જટિલતા ઓછામાં ઓછી સરેરાશ સાથે સબબ્રે શોધવા માટે

ઓ (એન) કારણ કે અમે ઇનપુટ સ્ટોર કરવા માટે એરેનો ઉપયોગ કર્યો હતો પરંતુ સોલ્યુશન ફક્ત સતત વધારાની જગ્યાનો ઉપયોગ કરે છે.