میانگین دامنه در آرایه


سطح دشواری متوسط
اغلب در کادنس هند Expedia شارژ رایگان خاکستری نارنجی Roblox Snapchat اسنپدل بار اینترنت 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،XNUMX،XNUMX،XNUMX که XNUMX است

(0,2،2,5,1) بنابراین مقدار متوسط ​​2،XNUMX،XNUMX،XNUMX که XNUMX است

(4,5،7,8) بنابراین مقدار متوسط ​​7،XNUMX،XNUMX،XNUMX که XNUMX است

میانگین دامنه در آرایه

 

الگوریتم

  1. یک آرایه PreMeanSum ایجاد کنید و اولین مقدار آن را به عنوان مقدار آرایه داده شده مقدار دهی کنید.
  2. آرایه را از 1 عبور داده و مجموع مقدار قبلی PreMeanSum و مقدار فعلی آرایه داده شده را در مقدار فعلی آرایه PreMeanSum ذخیره کنید.
  3. موقعیت جستجوی چپ و راست را بدست آورید و بررسی کنید که آیا موقعیت سمت چپ داده شده 0 است یا خیر ، در صورت درست بودن ، سپس ضریب PreMeanSum [راست] / راست + 1 را برگردانید.
  4. در غیر اینصورت مقدار PreMeanSum [راست] -PreMeanSum [چپ - 1] / راست - چپ +1 را بازگردانید.

توضیح

ما به یک آرایه عدد صحیح و تعداد پرسش ها داده ایم. بنابراین ، ما خواسته ایم مقدار کف میانگین اعدادی را که در محدوده داده شده اند برگردانیم. بنابراین ، یک رویکرد ساده که می تواند مانند هر پرس و جو دنبال شود ، ما آرایه را از نقطه شروع محدوده تا نقطه پایان محدوده رد می کنیم. و مجموع تمام مقادیر را در یک مقدار خاص ذخیره کنید. فرض کنید اگر باید میانگین (0 ، i) را پیدا کنیم. بنابراین در آن ar [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" تعداد پرسشهایی است که باید انجام شود زیرا میانگین می تواند در آن محاسبه شود O (1) پیچیدگی زمان O (N) زمان برای محاسبه PreMeanSum لازم است.

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است.