ശ്രേണിയിലെ ശ്രേണിയുടെ ശരാശരി


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു കഡെൻസ് ഇന്ത്യ ബൈ ഫ്രീചാർജ് ഗ്രേ ഓറഞ്ച് Roblox Snapchat സ്നാപ്ഡേൽ ടൈംസ് ഇന്റർനെറ്റ് യാൻഡക്സ്
അറേ അന്വേഷണ പ്രശ്നം

പ്രശ്നം പ്രസ്താവന

“ശ്രേണിയിലെ ശ്രേണിയുടെ ശരാശരി” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു പൂർണ്ണസംഖ്യ ശ്രേണി ഒപ്പം q ചോദ്യങ്ങളുടെ എണ്ണം. ഓരോ ചോദ്യത്തിലും ഇടതും വലതും ഒരു ശ്രേണിയായി അടങ്ങിയിരിക്കുന്നു. ഒരു നിശ്ചിത ശ്രേണിയിൽ വരുന്ന എല്ലാ സംഖ്യകളുടെയും ഫ്ലോർ മീഡിയൻ മൂല്യം കണ്ടെത്താൻ പ്രശ്‌ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു.

ഉദാഹരണം

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. ഒരു ശ്രേണി PreMeanSum സൃഷ്ടിച്ച് അതിന്റെ ആദ്യ മൂല്യം നൽകിയ അറേയുടെ മൂല്യമായി സമാരംഭിക്കുക.
  2. 1 ൽ നിന്ന് അറേയിലൂടെ സഞ്ചരിച്ച് പ്രീമീൻസമിന്റെ മുൻ മൂല്യത്തിന്റെ തുകയും തന്നിരിക്കുന്ന അറേയുടെ നിലവിലെ മൂല്യവും പ്രീമീൻസം അറേയുടെ നിലവിലെ മൂല്യത്തിലേക്ക് സംഭരിക്കുക.
  3. ചോദ്യത്തിന്റെ ഇടത്, വലത് സ്ഥാനം നേടുക, നൽകിയിരിക്കുന്ന ഇടത് സ്ഥാനം 0 ആണോയെന്ന് പരിശോധിക്കുക, ശരിയാണെങ്കിൽ പ്രീമീൻസം [വലത്] / വലത് + 1 ന്റെ ഘടകം നൽകുക.
  4. അല്ലാത്തപക്ഷം PreMeanSum [വലത്] -PreMeanSum [ഇടത് - 1] / വലത് - ഇടത് +1 ന്റെ മൂല്യം നൽകുക.

വിശദീകരണം

ഞങ്ങൾ ഒരു പൂർണ്ണ സംഖ്യയും ചോദ്യങ്ങളുടെ q നമ്പറും നൽകി. അതിനാൽ, നൽകിയിരിക്കുന്ന ശ്രേണിയിൽ വരുന്ന അക്കങ്ങളുടെ ശരാശരിയുടെ ഫ്ലോർ മൂല്യം തിരികെ നൽകാൻ ഞങ്ങൾ ആവശ്യപ്പെട്ടു. അതിനാൽ, ഓരോ ചോദ്യത്തിനും പോലെ ലളിതമായ ഒരു സമീപനം ഞങ്ങൾ ശ്രേണിയുടെ ആരംഭ പോയിന്റ് മുതൽ ശ്രേണിയുടെ അവസാന പോയിന്റ് വരെ ശ്രേണിയിലൂടെ സഞ്ചരിക്കും. എല്ലാ മൂല്യങ്ങളുടെയും ആകെത്തുക ഒരു പ്രത്യേക മൂല്യത്തിലേക്ക് സംഭരിക്കുക. (0, i) ന്റെ ശരാശരി കണ്ടെത്തേണ്ടതുണ്ടെങ്കിൽ എന്ന് കരുതുക. അതിനാൽ, [i], അറേ പൂജ്യത്തിൽ നിന്ന് നൽകിയിരിക്കുന്ന എല്ലാ മൂല്യങ്ങളും സംഗ്രഹിക്കേണ്ടതുണ്ട്. അതിനുശേഷം ആ തുകയുടെ ഘടകവും ആകെ മൂല്യങ്ങളുടെ എണ്ണവും ഞങ്ങൾ നൽകും.

എന്നാൽ അതിന്റെ ഒരു പോരായ്മ, നമുക്ക് n ചോദ്യങ്ങളുണ്ടെങ്കിൽ ഓരോ ചോദ്യത്തിനും നൽകിയിരിക്കുന്ന ശ്രേണിയിലേക്ക് നാം സഞ്ചരിക്കണം. ഇത് n സമയത്തിന്റെ എണ്ണം കടന്നുപോകും, ​​പക്ഷേ ഞങ്ങൾ അത് ഉപയോഗിക്കുന്ന സമീപനം ഓരോ ചോദ്യത്തിനും ഉത്തരം ഞങ്ങൾ ഒരു തവണ അറേ നിർമ്മിച്ചതിനുശേഷം സ്ഥിരമായ സമയത്ത് നൽകും.

ഞങ്ങൾ അറേ നിർമ്മിക്കും, അതിനായി ഞങ്ങൾ പ്രീമീൻസം അറേ അറേ പ്രഖ്യാപിച്ചു. തന്നിരിക്കുന്ന അറേയുടെ ആദ്യ മൂല്യമായി PreMeanSum അറേയുടെ ആദ്യ ഘടകം സമാരംഭിക്കുക. നമ്മൾ അറേ ഒന്നിൽ നിന്ന് അറേയുടെ നീളം വരെ സഞ്ചരിക്കും, അത് ചെയ്യുന്നതിന്റെ ഉദ്ദേശ്യം, സഞ്ചരിക്കുമ്പോൾ നിലവിലുള്ള മൂല്യത്തിലേക്ക് അടുത്തുള്ള രണ്ട് മൂല്യത്തിന്റെ തുക സംഭരിക്കേണ്ടതുണ്ട്. അതിനാലാണ് ഞങ്ങൾ ആ ആദ്യ മൂല്യം പകർത്തി 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n + q) എവിടെ "Q" എന്നത് കണക്കാക്കാൻ കഴിയുന്ന തരത്തിൽ നടത്തേണ്ട ചോദ്യങ്ങളുടെ എണ്ണം O (1) സമയ സങ്കീർണ്ണത. O (n) PreMeanSum പ്രീ കംപ്യൂട്ട് ചെയ്യാൻ സമയം ആവശ്യമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.