محدوده سeriesالات بدون به روزرسانی  


سطح دشواری ساده
اغلب در بلک راک GE بهداشت و درمان آزمایشگاه Moonfrog Synopsys Taxi4Sure Twilio
صف لارسن و توبرو مشکل پرس و جو

بیان مسأله  

مشکل "محدوده نمایش داده شد بدون به روزرسانی" بیان می کند که شما یک صف of عدد صحیح و یک دامنه بیانیه مسئله می خواهد از مجموع تمام عناصر موجود در محدوده مشخص شده مطلع شود.

مثال  

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

توضیح

مجموع تمام اعداد بین دامنه (0 ، 4) شامل 40 و مجموع تمام اعداد بین دامنه (1 ، 3) به طور 24 برابر است.

محدوده سeriesالات بدون به روزرسانی

 

الگوریتم  

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

توضیح  

ما یک آرایه از یک عدد صحیح و یک دامنه داده ایم ، از ما خواسته شده است که برای جمع بندی تمام پرسش ها از مجموع عناصر موجود در دامنه داده شده مطلع شویم. هر یک از پرس و جوها از یک محدوده به عنوان نقطه شروع و پایان یک محدوده تشکیل شده اند. این س anyال هیچ پرسشی برای به روزرسانی ندارد. این بدان معناست که در هنگام یافتن پاسخ پرسش ، نیازی به به روزرسانی هیچ یک از موارد نیست. ما فقط آرایه داده شده را خواهیم ساخت تا مجموع همه عناصر از 0 شاخص تا شاخص فعلی در موقعیت ith آرایه ساخته شده باشد. به این ترتیب ، هر پرس و جو با فضای اضافی O (n) در O (1) حل می شود.

همچنین مشاهده کنید
تعداد N عدد صحیح منحصر به فرد را تا Solution Leetcode Solution پیدا کنید

ما در حال ساخت sumArray ای هستیم که ایجاد کرده ایم. در این sumArray ، مجموع عناصر از 0 تا i در موقعیت یوم sumArray ذخیره می شود. ما این مقدار را محاسبه خواهیم کرد زیرا مقدار قبلی sumArray و مقدار فعلی آرایه داده شده را جمع می کنیم و هنگام پیمایش آن را در موقعیت شاخص فعلی sumArray ذخیره می کنیم. بنابراین وقتی کسی س askedال کرد مجموع تمام اعداد موجود در این موقعیت چقدر است ، ما فقط باید مقدار آن موقعیت را برای هر عنصر آرایه منحصر به فرد برگردانیم.

هنگامی که ما یک پرس و جو متشکل از هر محدوده دریافت خواهیم کرد ، و اگر نقطه سمت چپ یا شروع دامنه را برابر با 0 بدانیم ، ما فقط مقدار sumArray [سمت راست] را باز می گردانیم همان چیزی است که در بالا بحث کردیم ، آیا محدوده سمت چپ است برابر با 0 نیست ، تفاوت sumArray [راست] و sumArray [چپ-1] را برمی گردانیم. این پاسخ ها مورد نیاز خواهد بود. این روش همچنین یکی از ساده ترین راه هایی است که ما از آن استفاده می کنیم برنامه نویسی پویا.

رمز  

C ++ کد برای پرس و جوهای محدوده بدون به روزرسانی

#include<iostream>

using namespace std;

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

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

کد جاوا برای پرس و جوهای محدوده بدون به روزرسانی

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

تحلیل پیچیدگی  

پیچیدگی زمان

O (N + Q) ،  زیرا برای محاسبه زمان sumArray و سپس O (1) برای هر جستجو به O (N) نیاز داریم.

همچنین مشاهده کنید
چهار عنصر را پیدا کنید که در یک مقدار معین جمع می شوند (Hashmap)

پیچیدگی فضا

در اینجا ، در روش داده شده ، یک آرایه sumArray جدید ایجاد کرده ایم تا مجموع عناصر را از 0 تا i ذخیره کند. بنابراین این رویکرد نیاز دارد بر) فضا. اما می توانستیم آرایه اصلی را نیز اصلاح کنیم. سپس پیچیدگی فضا به ثابت کاهش می یابد.