એરેમાં રેન્જનો સરેરાશ


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે કેડન્સ ભારત એક્સપેડિયા ફ્રીચાર્જ ગ્રેઓરેંજ Roblox Snapchat સ્નેપડીલ ટાઇમ્સ ઇન્ટરનેટ યાન્ડેક્ષ
અરે ક્વેરી સમસ્યા

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

સમસ્યા "એરેમાં રેન્જનો સરેરાશ" જણાવે છે કે તમને એ પૂર્ણાંક એરે અને પ્રશ્નોની સંખ્યા. દરેક ક્વેરીમાં શ્રેણી તરીકે ડાબે અને જમણે સમાયેલ છે. સમસ્યા નિવેદન આપેલ શ્રેણીમાં આવતા તમામ પૂર્ણાંકોનું ફ્લોર સરેરાશ મૂલ્ય શોધવા માટે પૂછે છે.

ઉદાહરણ

array[] = {2, 5, 1, 6, 7, 8}

Query: {(1, 4), (0,2), (4,5)}
4 2 7

સમજૂતી

(1,4) તેથી 5,1,6,7 ની સરેરાશ કિંમત જે 4 છે

(0,2) તેથી 2,5,1 ની સરેરાશ કિંમત જે 2 છે

(4,5) તેથી 7,8 ની સરેરાશ કિંમત જે 7 છે

એરેમાં રેન્જનો સરેરાશ

 

અલ્ગોરિધમ

  1. એક એરે પ્રિમેનસમ બનાવો અને આપેલ એરેના મૂલ્ય તરીકે તેનું પ્રથમ મૂલ્ય પ્રારંભ કરો.
  2. એરેને 1 થી પરિવર્તિત કરો અને પ્રીમિનસમના પાછલા મૂલ્યનો સરવાળો અને આપેલ એરેના વર્તમાન મૂલ્યને પ્રીમિનસમ એરેના વર્તમાન મૂલ્યમાં સંગ્રહિત કરો.
  3. ક્વેરીની ડાબી અને જમણી પોઝિશન મેળવો અને જો આપેલ ડાબી પોઝિશન 0 છે કે નહીં તે તપાસો, જો સાચું હોય તો PreMeanSum [જમણે] / જમણે + 1 નો ભાગ પાછો આપો
  4. બાકી પ્રીમમેનસમનું મૂલ્ય પાછું [જમણે] -પ્રેમિનસમ [ડાબે - 1] / જમણે - ડાબે +1.

સમજૂતી

આપણે પૂર્ણાંક એરે અને પ્રશ્નોની સંખ્યા આપી છે. તેથી, અમે આપેલ શ્રેણીમાં આવતા નંબરોના સરેરાશનું ફ્લોર મૂલ્ય પાછા આપવાનું કહ્યું છે. આમ, એક સરળ અભિગમ કે જે દરેક ક્વેરી માટે અનુસરી શકાય છે જેમ કે આપણે એરેને શ્રેણીના પ્રારંભિક બિંદુથી અંતિમ બિંદુ સુધી જઈશું. અને બધા મૂલ્યોનો સરવાળો કોઈ ચોક્કસ મૂલ્યમાં સંગ્રહિત કરો. ધારો કે જો આપણે (0, i) નો અર્થ શોધવો પડશે. તેથી એરે [i], આપણે એરે શૂન્યથી આપેલા ith મૂલ્ય સુધીના તમામ મૂલ્યોનો સારાંશ આપવો પડશે. પછી આપણે તે રકમનો ભાગ અને કિંમતોની કુલ સંખ્યા, જેમાંથી સરવાળો કરવામાં આવશે તે પરત આપીશું.

પરંતુ તેનો એક ગેરલાભ એ છે કે જો આપણી પાસે એન ક્વેરીઝ હોય તો આપણે દરેક ક્વેરી માટે આપેલી રેન્જ માટે પસાર થવું પડશે. તે સમયની n સંખ્યાને વટાવી દેશે, પરંતુ આપણે તેનો ઉપયોગ કરી રહ્યા છીએ તે અભિગમ આપણે એકવાર એરે બનાવીશું તે પછી દરેક ક્વેરીનો જવાબ સતત સમયમાં પાછો આપશે.

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

કોડ

એરેમાં સરેરાશનો વિસ્તાર શોધવા માટે સી ++ કોડ

#include<iostream>
#include<math.h>

#define MAX 1000005
using namespace std;

int PreMeanSum[MAX];

void buildPreMean(int arr[], int n)
{
    PreMeanSum[0] = arr[0];
    for (int i = 1; i < n; i++)
        PreMeanSum[i] = PreMeanSum[i - 1] + arr[i];
}

int getMeanInRange(int l, int r)
{
    if (l == 0)
        return floor(PreMeanSum[r] / (r + 1));

    return floor( (PreMeanSum[r] - PreMeanSum[l - 1]) / (r - l + 1));
}

int main()
{

    int arr[] = {2,5,1,6,7,8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    buildPreMean(arr, n);
    cout << getMeanInRange(1, 4) << endl;
    cout << getMeanInRange(0, 2) << endl;
    cout << getMeanInRange(4, 5) << endl;
    return 0;
}
4
2
7

એરેમાં સરેરાશનો વિસ્તાર શોધવા માટે જાવા કોડ

class MeanInRange
{
    public static final int MAX = 1000005;

    static int PreMeanSum[] = new int[MAX];

    static void buildPreMean(int arr[], int n)
    {
        PreMeanSum[0] = arr[0];
        for (int i = 1; i < n; i++)
            PreMeanSum[i] = PreMeanSum[i - 1] + arr[i];
    }

    static int getMeanInRange(int l, int r)
    {
        if (l == 0)
            return (int)Math.floor(PreMeanSum[r] / (r + 1));

        return (int)Math.floor((PreMeanSum[r] -
                                PreMeanSum[l - 1]) / (r - l + 1));
    }

    public static void main(String[] args)
    {
        int arr[] = {2,5,1,6,7,8 };
        int n = arr.length;
        buildPreMean(arr, n);
        System.out.println(getMeanInRange(1, 4));
        System.out.println(getMeanInRange(0, 2));
        System.out.println(getMeanInRange(4, 5));
    }
}
4
2
7

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

સમય જટિલતા

ઓ (એન + ક્યૂ) જ્યાં "ક્યૂ" સરેરાશ ગણતરી કરી શકાતી ક્વેરીઝની સંખ્યા છે ઓ (1) સમય જટિલતા. ઓ (એન) પ્રીમિનસમ પૂર્વવત્ કરવા માટે સમય આવશ્યક છે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.