अ‍ॅरे मधील श्रेणीचा मध्यम  


अडचण पातळी मध्यम
वारंवार विचारले कॅडन्स इंडिया यामध्ये फ्रीचार्ज ग्रेऑरेंज Roblox Snapchat Snapdeal टाइम्स इंटरनेट यांडेक्स
अरे क्वेरी समस्या

समस्या विधान  

"अ‍ॅरे मधील श्रेणीचा मध्यम" समस्या असे सांगते की आपल्याला एक दिले गेले आहे पूर्णांक अॅरे आणि प्रश्नांची संख्या प्रत्येक क्वेरीमध्ये श्रेणी म्हणून डावे आणि उजवे असतात. प्रॉब्लेम स्टेटमेंट दिलेल्या श्रेणीत येणा the्या सर्व पूर्णांकाची मजल्याची सरासरी मूल्य शोधण्यास सांगते.

उदाहरण  

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 आहे की नाही ते तपासा, खरे असल्यास प्रीमॅनसम [उजवीकडे] / उजवे + 1 असा भाग द्या.
  4. अन्यथा प्रीमॅनसम [उजवीकडे] -प्रीमॅनसम [डावे - 1] / उजवीकडे - डावे +1 चे मूल्य परत करा.

स्पष्टीकरण

आम्ही पूर्णांक अ‍ॅरे आणि क्यू संख्या संख्या दिली आहेत. म्हणून आम्ही दिलेल्या श्रेणीत येणा the्या संख्येच्या मूळचे फर्श मूल्य परत करण्यास सांगितले आहे. अशाप्रकारे, एक सोपा दृष्टिकोन अनुसरण केला जाऊ शकतो ज्याप्रमाणे प्रत्येक क्वेरीसाठी आपण श्रेणीच्या सुरूवातीपासून ते शेवटच्या बिंदूपर्यंत अ‍ॅरेचा शोध घेत आहोत. आणि सर्व मूल्यांची बेरीज एका विशिष्ट मूल्यात संचयित करा. समजा जर आपल्याला (0, i) चा अर्थ शोधायचा असेल तर. म्हणजे एर [i], आपल्याला अ‍ॅरे शून्यापासून दिलेल्या इथ व्हॅल्यूपर्यंत सर्व मूल्यांचा सारांश द्यावा लागेल. तर आम्ही त्या बेरीजचा भाग आणि एकूण मूल्यांची संख्या, जे बेरीज केले आहे परत करू.

हे सुद्धा पहा
पुढील ग्रेटर फ्रीक्वेंसी एलिमेंट

परंतु त्यातील एक तोटा म्हणजे आपल्याकडे क्वेरी असल्यास प्रत्येक क्वेरीसाठी दिलेल्या श्रेणीसाठी जाणे आवश्यक आहे. हे वेळेच्या क्रमांकावर जाईल, परंतु आपण ज्या अ‍ॅप्रो वापरत आहोत त्याचा उपयोग एकदा अ‍ॅरे बनविल्यानंतर प्रत्येक क्वेरीचे उत्तर स्थिर वेळेत परत करेल.

आपण अ‍ॅरे बनवित आहोत. त्यासाठी आपण प्रीमॅनसम अ‍ॅरे घोषित केला आहे. नंतर दिलेल्या अ‍ॅरेचे प्रथम मूल्य म्हणून प्रीमॅनसम अ‍ॅरेचा पहिला घटक प्रारंभ करा. आपण अ‍ॅरेची लांबी एकापासून मागे जाऊ, हे करण्याचा हेतू असा आहे की ट्रॅव्हर्सिंग करताना आपल्याला दोन समीप मूल्याची बेरीज वर्तमान व्हॅल्यूमध्ये संचित करावी लागेल. म्हणूनच आम्ही प्रथम मूल्य कॉपी केले आहे आणि 1 पासून प्रारंभ करीत आहोत. आम्हाला प्रारंभ बिंदू आणि अंतिम बिंदू म्हणून श्रेणी प्राप्त होईल. त्यानंतर दिलेले डावे मूल्य ० बरोबर असल्यास तपासू, जर सत्य असेल तर प्रीमॅनसम [उजवीकडे] / उजवे + १ विभागणी परत करा, फक्त बेरीज / एकूण मूल्यांची संख्या. नाहीतर आम्ही प्रीमॅनसम [उजवीकडे] -प्रेमॅनसम [डावे -0] आणि उजवे-डावे + 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

गुंतागुंत विश्लेषण  

वेळ कॉम्प्लेक्सिटी

ओ (एन + क) जेथे "Q" क्षुद्र गणना केली जाऊ शकते म्हणून केले जाणारे क्वेरींची संख्या आहे ओ (1) वेळ गुंतागुंत. O (n) प्रीमॅनसम सुरू करण्यासाठी वेळ आवश्यक आहे.

हे सुद्धा पहा
क्रमवारी लावलेल्या अ‍ॅरेमध्ये शोधा

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.