ព្រីនធ័រដែលបានកែប្រែបន្ទាប់ពីប្រតិបត្ដិការបង្កើនជួរអារេជាច្រើន


កម្រិតលំបាក រឹង
សួរញឹកញាប់ Expedia FreeCharge ក្រុមហ៊ុន google ជា​ការ​ពិត មន្ទីរពិសោធន៍ Moonfrog អូឡាកាប Qualtrics
អារេ បញ្ហាសំណួរ

បញ្ហា“ ព្រីនព្រីនដែលបានកែប្រែបន្ទាប់ពីប្រតិបត្ដិការបង្កើនជួរជាច្រើន” ដែលអ្នកត្រូវបានផ្តល់ឱ្យ integer អារេ និង 'q' ចំនួនសំណួរត្រូវបានផ្តល់។ តម្លៃចំនួនគត់មួយ“ ឃ” ក៏ត្រូវបានផ្តល់ផងដែរ។ សំណួរនីមួយៗមានចំនួនគត់ពីរគឺតម្លៃចាប់ផ្តើមនិងតម្លៃបញ្ចប់។ សេចក្តីថ្លែងបញ្ហាស្នើឱ្យស្វែងរកការបង្កើនតម្លៃទាំងអស់នៅក្នុងជួរដែលស្ថិតនៅក្នុងជួរដែលបានផ្តល់ដោយតម្លៃ“ ឃ” ។ បោះពុម្ពអារេដែលបានកែប្រែ។

ឧទាហរណ៍

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. ឆ្លងកាត់អារេពី ០ ទៅចំនួនសំណួរសរុប។
  3. បន្ថែមតម្លៃដែលបានផ្តល់នៅក្នុងអារេដែលយើងបានបង្កើតទៅជួរដែលបានផ្តល់។ ពិនិត្យមើលថាតើជួរបញ្ចប់នៃសំណួរដែលបានផ្តល់ឱ្យតិចជាងប្រវែងអារេ។ បើពិតបន្ថយតម្លៃ“ ឃ” ពីអារេដែលយើងបានបង្កើត។
  4. ឆ្លងកាត់អារេដែលបានផ្តល់ហើយធ្វើបច្ចុប្បន្នភាពអារេលទ្ធផលជាមួយនឹងការបន្ថែមនៃចរន្តនិងតម្លៃមុននិងអារេដែលបានផ្តល់។
  5. បោះពុម្ពអារេដែលបានធ្វើបច្ចុប្បន្នភាព។

ការពន្យល់

ដែលបានផ្តល់ឱ្យ អារេ of integer និងមួយចំនួននៃសំណួរ, សំណួរគ្នាមានជួរចាប់ផ្តើមនិងបញ្ចប់និងតម្លៃដែលបានផ្តល់ឱ្យ។ យើងត្រូវបន្ថែមតម្លៃដែលបានផ្តល់ឱ្យលេខទាំងអស់ចាប់ពីចំណុចចាប់ផ្តើមរហូតដល់ចំណុចបញ្ចប់នៃជួរដែលបានផ្តល់។ យើងនឹងបង្កើតសំណួរជាច្រើន។ លេខពីរនៃលេខនឹងត្រូវបានភ្ជាប់ជាមួយអារេនីមួយៗនៃសំណួរ។ យើងនឹងបង្កើតអារេបន្ថែមដែលមានទំហំដូចគ្នានឹងប្រវែងនៃអារេដែលបានផ្តល់ឱ្យ។ យើងនឹងអនុវត្តប្រតិបត្តិការនៅលើអារេនេះហើយបន្ទាប់មកធ្វើបច្ចុប្បន្នភាពប្រតិបត្តិការទាំងនេះលើអារេដែលបានផ្តល់ឱ្យ។

ឥឡូវនេះយើងដំណើរការរង្វិលជុំរហូតដល់ចំនួនសំណួរ។ យើងនឹងធ្វើបច្ចុប្បន្នភាពអារេលទ្ធផលជាមួយនឹងការបន្ថែមតម្លៃដែលបានផ្តល់ 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 " គឺជាចំនួនសំណួរ។ ដោយសារយើងបានប្រើវិធីដូចជាផលបូកបុព្វបទយើងមានពេលវេលាស្មុគស្មាញ។

ភាពស្មុគស្មាញនៃលំហ

 អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។