අරාවෙහි පරාසයේ මධ්‍යන්‍යය


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ කේඩන්ස් ඉන්දියාව Expedia FreeCharge ග්‍රේ ඔරේන්ජ් Roblox Snapchat Snapdeal ටයිම්ස් අන්තර්ජාලය Yandex
අරා විමසුම් ගැටළුව

ගැටළු ප්රකාශය

“අරාවේ පරාසයේ මධ්‍යන්‍යය” යන ගැටලුවේ සඳහන් වන්නේ ඔබට ලබා දී ඇති බවයි නිඛිල අරාව සහ 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 සිට අරාව හරහා ගමන් කර PreMeanSum හි පෙර අගය හා ලබා දී ඇති අරාවේ වත්මන් අගය PreMeanSum අරාවේ වත්මන් අගයට ගබඩා කරන්න.
  3. විමසුමේ වමේ සහ දකුණේ පිහිටීම ලබා දී වම් ස්ථානය 0 දැයි පරීක්ෂා කරන්න, සත්‍ය නම් PreMeanSum [දකුණේ / දකුණ + 1 හි කොටස ආපසු එවන්න.
  4. PreMeanSum [දකුණේ] -PreMeanSum [වමේ - 1] / දකුණ - වමේ +1 හි අගය නැවත ලබා දෙන්න.

පැහැදිලි කිරීම

අපි පූර්ණ සංඛ්‍යා පෙළක් සහ q විමසුම් සංඛ්‍යාවක් ලබා දී ඇත. එබැවින්, ලබා දී ඇති පරාසය තුළ එන සංඛ්‍යා වල මධ්‍යන්‍යයේ බිම් වටිනාකම නැවත ලබා දෙන ලෙස අපි ඉල්ලා සිටිමු. මේ අනුව, සෑම විමසුමකටම මෙන් අනුගමනය කළ හැකි සරල ප්‍රවේශයක් අපි පරාසයේ ආරම්භක ස්ථානයේ සිට පරාසයේ අවසානය දක්වා අරාව හරහා ගමන් කරන්නෙමු. සියලු අගයන්හි එකතුව යම් අගයකට ගබඩා කරන්න. (0, i) හි මධ්‍යන්‍යය අපට සොයාගත යුතු යැයි සිතමු. ඒ නිසා අරාව [i], අරාව ශුන්‍යයේ සිට ලබා දී ඇති ith අගය දක්වා සියලු අගයන් සාරාංශ කිරීමට අපට සිදුවේ. එවිට අපි එම මුදලේ ප්‍රමාණය සහ මුළු අගයන් ගණන ආපසු ලබා දෙන්නෙමු.

නමුත් එහි එක් අවාසියක් නම්, අපට විමසුම් n තිබේ නම්, එක් එක් විමසුම සඳහා ලබා දී ඇති පරාසය සඳහා ගමන් කළ යුතුය. එය n ගණන හරහා ගමන් කරනු ඇත, නමුත් අප එය භාවිතා කරන ප්‍රවේශය මඟින් අපි එක් වරක් අරාව සෑදූ පසු එක් එක් විමසුමේ පිළිතුර නියත වේලාවට ලබා දෙනු ඇත.

අපි අරාව ගොඩනඟමු, ඒ සඳහා අපි අරා PreMeanSum අරාව ප්‍රකාශයට පත් කර ඇත්තෙමු. ඉන්පසු ලබා දී ඇති අරාවේ පළමු අගය ලෙස PreMeanSum අරාවේ පළමු අංගය ආරම්භ කරන්න. අපි අරාව එක සිට දිග දක්වා ගමන් කරන්නෙමු, එය සිදු කිරීමේ අරමුණ වන්නේ අප ගමන් කරන අතරතුර යාබද අගයන් දෙකක එකතුව වත්මන් අගයට ගබඩා කිරීමයි. අපි පළමු අගය පිටපත් කර 1 සිට ආරම්භ කර ඇත්තේ එබැවිනි. අපට පරාසය ආරම්භක ලක්ෂ්‍යයක් සහ අවසන් ලක්ෂ්‍යයක් ලෙස ලැබෙනු ඇත. ඉන් පසුව අපි පරික්ෂා කරනුයේ ලබා දී ඇති වම් අගය 0 ට සමානද, සත්‍ය නම්, PreMeanSum [දකුණ] / දකුණ + 1 බෙදීම නැවත ලබා දෙන්න, එකතුව / මුළු අගයන් ගණන. නැතහොත් අපි PreMeanSum [දකුණේ -PreMeanSum [වමේ -1] සහ දකුණු-වම් + 1 හි වෙනස බෙදන්නෙමු. එය අවශ්‍ය පිළිතුර වනු ඇත.

කේතය

අරාවේ පරාසයේ මධ්‍යන්‍යය සොයා ගැනීමට C ++ කේතය

#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" ගණනය කළ හැකි මධ්‍යන්‍ය ලෙස සිදු කළ යුතු විමසුම් ගණන ඕ (1) කාල සංකීර්ණත්වය. සාමාන්ය (n) PreMeanSum පූර්ව ගණනය කිරීමට කාලය අවශ්‍ය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.