طباعة صفيف معدل بعد عمليات زيادة نطاق الصفيف المتعددة


مستوى الصعوبة الثابت
كثيرا ما يطلب في اكسبيديا شحن مجاني جوجل في الواقع مختبرات 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) سيكون العائد {7 ، 3 ، 4 ، 7 ، 9 ، XNUMX}

الآن الزيادة من الفهرس (3,5،2) ستصبح {7، 3، 6، 9، 11، XNUMX}

الزيادة مرة أخرى من الفهرس (4,5،2) ستكون القيمة {7 ، 3 ، 6 ، 11 ، 13 ، XNUMX}

الآن الزيادة من الفهرس (2,4،2) ستصبح {7، 5، 8، 13، 13، XNUMX}

الزيادة مرة أخرى من الفهرس (1,3،2) ستكون القيمة {9 ، 7 ، 10 ، 13 ، 13 ، XNUMX}

 

طباعة صفيف معدل بعد عمليات زيادة نطاق الصفيف المتعددة

خوارزمية لعمليات زيادة نطاق الصفيف المتعددة

  1. قم بتعريف مصفوفة بنفس حجم المصفوفة المحددة.
  2. اجتياز المصفوفة من 0 إلى إجمالي عدد الاستعلامات.
  3. أضف القيمة المحددة في المصفوفة التي أنشأناها إلى النطاق المحدد. تحقق مما إذا كان نطاق النهاية للاستعلام المحدد أقل من طول المصفوفة. إذا كان هذا صحيحًا ، قلل القيمة "d" من المصفوفة التي أنشأناها.
  4. اجتياز المصفوفة المحددة وتحديث مصفوفة الإخراج بإضافة القيم الحالية والسابقة والمصفوفة المحددة.
  5. اطبع المصفوفة المحدثة.

تفسير

نظرا ل مجموعة of عدد صحيح وعدد من الاستعلامات ، يحتوي كل استعلام على نطاق البداية والنهاية وقيمة معينة. علينا جمع القيمة المعطاة لجميع الأرقام من نقطة البداية إلى نقطة النهاية في النطاق المحدد. سنقوم بإنشاء مجموعة من الاستفسارات. سيتم إقران رقمين مع كل مصفوفة من مصفوفة الاستعلام. سننشئ مصفوفة إضافية بنفس حجم طول المصفوفة المحددة. سنقوم بتنفيذ العمليات على هذه المصفوفة ثم نقوم بتحديث هذه العمليات على المصفوفة المحددة.

الآن نقوم بتشغيل حلقة حتى عدد الاستفسارات. سنقوم بتحديث مصفوفة الإخراج بإضافة القيمة المحددة 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

كود Java لطباعة مجموعة معدلة بعد عمليات زيادة نطاق الصفيف المتعددة

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 (ن) أين "ن" هو عدد العناصر في الصفيف.