آرایه اصلاح شده را پس از چندین عملیات افزایش دامنه آرایه چاپ کنید


سطح دشواری سخت
اغلب در Expedia شارژ رایگان گوگل در واقع آزمایشگاه Moonfrog کابین های اولا Qualtrics
صف مشکل پرس و جو

مسئله "چاپ آرایه اصلاح شده پس از چندین عملیات افزایش دامنه آرایه" بیان می کند که به شما یک داده می شود عدد صحیح صف و تعداد 'q' از پرس و جوها آورده شده است. یک مقدار صحیح "d" نیز داده شده است. هر پرس و جو شامل دو عدد صحیح است ، مقدار شروع و مقدار پایان. با بیان مسئله می خواهیم همه مقادیر آرایه را در محدوده داده شده با مقدار "d" افزایش دهیم. آرایه اصلاح شده را چاپ کنید.

مثال

arr[] = {2, 5, 1, 4, 7, 9}
Query: (1, 2), (3, 5), (4, 5), (2, 4), (1, 3)
d = 2
2 9 7 10 13 13

توضیح

پس از افزایش از شاخص (1,2،2) arr {7 ، 3 ، 4 ، 7 ، 9 ، XNUMX} خواهد بود

اکنون افزایش از فهرست (3,5،2) arr به {7 ، 3 ، 6 ، 9 ، 11 ، XNUMX} تبدیل می شود

بازهم افزایش از شاخص (4,5،2) عقب خواهد بود {7 ، 3 ، 6 ، 11 ، 13 ، XNUMX}

اکنون افزایش از فهرست (2,4،2) arr به {7 ، 5 ، 8 ، 13 ، 13 ، XNUMX} تبدیل می شود

بازهم افزایش از شاخص (1,3،2) عقب خواهد بود {9 ، 7 ، 10 ، 13 ، 13 ، XNUMX}

 

آرایه اصلاح شده را پس از چندین عملیات افزایش دامنه آرایه چاپ کنید

الگوریتم عملیات افزایش دامنه آرایه های متعدد

  1. آرایه ای را به همان اندازه آرایه داده شده اعلام کنید.
  2. آرایه را از 0 به تعداد کل درخواستها رد کنید.
  3. مقدار داده شده را در آرایه ای که ایجاد کردیم به محدوده داده شده اضافه کنید. بررسی کنید دامنه پایان پرس و جو داده شده کمتر از طول آرایه باشد. اگر درست است ، مقدار "d" را از آرایه ای که ایجاد کردیم کاهش دهید.
  4. آرایه داده شده را رد کنید و آرایه خروجی را با اضافه کردن جریان و مقادیر قبلی و آرایه داده شده به روز کنید.
  5. آرایه به روز شده را چاپ کنید.

توضیح

با توجه به صف of عدد صحیح و تعدادی از پرس و جوها ، هر پرسش شامل دامنه شروع و پایان و یک مقدار مشخص است. ما باید مقدار داده شده را به همه اعداد از نقطه شروع تا نقطه پایان محدوده داده شده اضافه کنیم. ما یک آرایه از query ها ایجاد خواهیم کرد. دو عدد با هر یک از آرایه های جستجو مرتبط می شوند. ما یک آرایه اضافی با همان اندازه آرایه داده شده ایجاد خواهیم کرد. ما عملیات مربوط به این آرایه را انجام می دهیم و سپس این عملیات را روی آرایه داده شده به روز می کنیم.

حالا یک حلقه اجرا می کنیم تا تعداد نمایش داده ها. ما آرایه خروجی را با اضافه کردن مقدار داده شده به روز خواهیم کرد d، در فهرست شروع پرس و جو. بررسی کنید که آیا مقدار پایان پرس و جو از طول آرایه کمتر است. اگر مشخص شد که اگر درست باشد درست است پس d را از مقدار به روز شده قبلی در آرایه خروجی کاهش دهید. این برای اطمینان از این است که از محدوده و مقادیر خارج نخواهیم شد.

اکنون ، ما می خواهیم اولین موقعیت آرایه داده شده را به موقعیت اول آرایه خروجی به روز کنیم. زیرا ما قصد داریم مقادیر قبلی آرایه حاصل جمع (یا خروجی) و مقدار فعلی را پیمایش کنیم. بنابراین ما در حال حاضر اولین مقدار را به روز کرده و اکنون از موقعیت اول آرایه خروجی تا انتها عبور می کنیم. ما می خواهیم مقدار قبلی و فعلی را جمع کرده و در آرایه خروجی ذخیره کنیم. در هنگام پیمایش ، آن مقدار را در موقعیتهای مربوط به آرایه داده شده کپی کنید. آرایه اصلاح شده را چاپ کنید.

رمز

کد ++ C برای چاپ آرایه اصلاح شده پس از چندین عملیات افزایش دامنه آرایه

#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

struct query
{
    int start, end;
};

void incrementByD(int arr[], struct query q_arr[],int n, int m, int d)
{
    int sum[n];
    memset(sum, 0, sizeof(sum));

    for (int i = 0; i < m; i++)
    {
        sum[q_arr[i].start] += d;

        if ((q_arr[i].end + 1) < n)
            sum[q_arr[i].end + 1] -= d;
    }
    arr[0] += sum[0];
    for (int i = 1; i < n; i++)
    {
        sum[i] += sum[i - 1];
        arr[i] += sum[i];
    }
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main()
{
    int arr[] = {2, 5, 1, 4, 7, 9};
    struct query q_arr[] = { { 1, 2 }, { 3, 5 },  {4,5 },
        { 2, 4 }, { 1, 3 }
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = sizeof(q_arr) / sizeof(q_arr[0]);

    int d = 2;

    cout << "Original Array:\n";
    printArray(arr, n);

    incrementByD(arr, q_arr, n, m, d);

    cout << "\nModified Array:\n";
    printArray(arr, n);

    return 0;
}
Original Array:
2 5 1 4 7 9
Modified Array:
2 9 7 10 13 13

کد جاوا برای چاپ آرایه اصلاح شده پس از چندین عملیات افزایش دامنه آرایه

class modifiedArray
{
    static class query
    {
        int start, end;

        query(int start, int end)
        {
            this.start = start;
            this.end = end;
        }
    }

    public static void incrementByD(int[] arr, query[] q_arr, int n, int m, int d)
    {
        int[] sum = new int[n];

        for (int i = 0; i < m; i++)
        {
            sum[q_arr[i].start] += d;

            if ((q_arr[i].end + 1) < n)
                sum[q_arr[i].end + 1] -= d;
        }
        arr[0] += sum[0];
        for (int i = 1; i < n; i++)
        {
            sum[i] += sum[i - 1];
            arr[i] += sum[i];
        }
    }

    public static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }

    public static void main(String[] args)
    {
        int[] arr = { 2, 5, 1, 4, 7, 9};
        query[] q_arr = {new query(1, 2),new query(3,5),new query(4, 5),
                  new query(2, 4),new query(1, 3)
        };

        int n = arr.length;
        int m = q_arr.length;
        int d = 2;
        System.out.println("Original Array:");
        printArray(arr, n);

        incrementByD(arr, q_arr, n, m, d);
        System.out.println("\nModified Array:");
        printArray(arr, n);
    }
}
Original Array:
2 5 1 4 7 9
Modified Array:
2 9 7 10 13 13

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

پیچیدگی زمان

 O (q + n) جایی که "n" تعداد عناصر آرایه است و "q” تعداد سeriesالات است. از آنجا که ما از رویکردی مانند جمع پیشوند استفاده کرده ایم ، از پیچیدگی زمانی خطی برخوردار هستیم.

پیچیدگی فضا

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