អារេខុសគ្នា | ជួរធ្វើបច្ចុប្បន្នភាពសំណួរជាអូ (១)  


កម្រិតលំបាក រឹង
សួរញឹកញាប់ អាសេស្យូម លេខកូដ Directi Expedia ក្រុមហ៊ុន google ក្រុមហ៊ុន qualcomm
អារេ បញ្ហាសំណួរ

អ្នកត្រូវបានផ្តល់ឱ្យ integer អារេ និងសំណួរពីរប្រភេទមួយគឺត្រូវបន្ថែមលេខដែលបានផ្តល់ឱ្យនៅក្នុងជួរមួយនិងមួយទៀតដើម្បីបោះពុម្ពអារេទាំងមូល។ បញ្ហា“ អារេខុសគ្នា | សំណួរធ្វើបច្ចុប្បន្នភាពជួរនៅក្នុងអូ (១)” តម្រូវឱ្យយើងអនុវត្តការធ្វើបច្ចុប្បន្នភាពជួរនៅក្នុងអូ (១) ។

ឧទាហរណ៍  

arr[] = {20, 30, 25, 50}

Update(0, 1, 10)

print()

update(0, 2, 20)

update(2, 3, 30)

print()
(30 40 25 50) (50 60 75 80)

ការពន្យល់

១០ នឹងត្រូវបន្ថែមទៅ ២០ និង ៣០ ដូច្នេះអារេនឹងក្លាយជា {៣០, ៤០, ២៥, ៥០}

បន្ទាប់មកយើងនឹងបោះពុម្ពអារេទាំងមូល។

២០ នឹងត្រូវបន្ថែមទៅ ៣០, ៤០ និង ២៥ ដូច្នេះអារេនឹងក្លាយជា {៥០, ៦០, ៤៥, ៥០}

១០ នឹងត្រូវបន្ថែមទៅ ២០ និង ៣០ ដូច្នេះអារេនឹងក្លាយជា {៣០, ៤០, ២៥, ៥០}

បន្ទាប់មកម្តងទៀតយើងនឹងបោះពុម្ពអារេទាំងមូល។

តម្លៃពីរឈុតនឹងត្រូវបានបោះពុម្ពបន្ទាប់ពីបំពេញសំណួរ។

អារេខុសគ្នា | ជួរធ្វើបច្ចុប្បន្នភាពសំណួរជាអូ (១)

 

ក្បួនដោះស្រាយសម្រាប់អារេភាពខុសគ្នា  

  1. បង្កើតអារេមួយដែលមានទំហំដូចគ្នានឹងអារេដែលបានផ្តល់ឱ្យ។
  2. បង្កើតលិបិក្រមដំបូងដែលជាធាតុទីមួយរបស់អារេហើយលិបិក្រមចុងក្រោយជាមួយ ០ ហើយសូចនាករផ្សេងទៀតទាំងអស់ត្រូវបានបំពេញដោយភាពខុសគ្នានៃធាតុបច្ចុប្បន្ននិងមុន។
  3. សម្រាប់រាល់សំណួរបច្ចុប្បន្នភាពបន្ថែមតម្លៃ X ទៅសន្ទស្សន៍ខាងឆ្វេងដែលបានផ្តល់ឱ្យនៃអារេដែលបានបង្កើតហើយដក X ពីសន្ទស្សន៍ខាងស្តាំនៃអារេដែលបានបង្កើត។
  4. សម្រាប់រាល់សំណួរបោះពុម្ពដំបូងយើងបំពេញជួរបញ្ចូលដោយប្រើរូបមន្ត A [i] = D [i] + A [i-1] ។ បន្ទាប់មកបោះពុម្ពតម្លៃ។
សូម​មើល​ផង​ដែរ
ដែលបានផ្តល់ឱ្យអារេដែលមិនមានជួរពីររកឃើញគូទាំងអស់ដែលជាផលបូកគឺ x

ការពន្យល់  

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

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

យើងនឹងទទួលបានតម្លៃជាជួរប្រសិនបើយើងទទួលបានសំណួរធ្វើបច្ចុប្បន្នភាព។ រួមជាមួយយើងក៏ត្រូវបានផ្តល់ជូននូវលេខផងដែរ។ បន្ទាប់មកយើងនឹងបន្ថែមលេខនោះនៅសន្ទស្សន៍ខាងឆ្វេងនៃជួរនៅក្នុងអារេខុសគ្នា។ ស្រដៀងគ្នានេះដែរដកតម្លៃ X ពីសន្ទស្សន៍ខាងស្តាំនៃអារេខុសគ្នា។ សម្រាប់ការបោះពុម្ពអារេយើងនឹងឆ្លងកាត់អារេហើយសម្រាប់តម្លៃសន្ទស្សន៍សូន្យយើងនឹងធ្វើបច្ចុប្បន្នភាពតម្លៃនៃអារេដែលបានផ្តល់ជាអារេដែលយើងបានបង្កើតបើមិនដូច្នេះទេយើងនឹងទទួលបានផលបូកនៃអារេដែលបានបង្កើតនិងតម្លៃមុននៃអារេដែលបានផ្តល់ហើយ បោះពុម្ពតម្លៃនោះសម្រាប់សន្ទស្សន៍ជាក់លាក់។

សូម​មើល​ផង​ដែរ
ចំនួនសន្ទស្សន៍ដែលមានធាតុស្មើគ្នានៅក្នុងជួរដែលបានផ្តល់

លេខកូដ  

ការអនុវត្តនៅក្នុង C ++ សម្រាប់អារេខុសគ្នា

#include<iostream>

using namespace std;

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

static void update(int dummyArray[], int l, int r, int x)
{
    dummyArray[l] += x;
    dummyArray[r + 1] -= x;
}

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

        if (i == 0)
            arr[i] = dummyArray[i];
        else
            arr[i] = dummyArray[i] + arr[i - 1];

        cout<<arr[i] << " ";
    }

    cout<<endl;
}

int main()
{
    int arr[] = {20,30,25,50};
    int n = sizeof(arr)/sizeof(arr[0]);

    int dummyArray[n + 1];
    buildArray(arr, dummyArray, n);

    update(dummyArray, 0, 1, 10);
    printArray(arr, dummyArray, n);
    update(dummyArray, 0, 2, 20);
    update(dummyArray, 2, 3, 30);

    printArray(arr, dummyArray,n);
    return 0;
}
30 40 25 50
50 60 75 80

ការអនុវត្តនៅចាវ៉ាសម្រាប់អារេខុសគ្នា

class differenceArray
{
    static void buildArray(int arr[], int dummyArray[])
    {

        int n = arr.length;

        dummyArray[0] = arr[0];
        dummyArray[n] = 0;
        for (int i = 1; i < n; i++)
            dummyArray[i] = arr[i] - arr[i - 1];
    }
    
    static void update(int dummyArray[], int left, int right, int x)
    {
        dummyArray[left] += x;
        dummyArray[right + 1] -= x;
    }
    
    static int printArray(int arr[], int dummyArray[])
    {
        for (int i = 0; i < arr.length; i++)
        {
            if (i == 0)
                arr[i] = dummyArray[i];
            else
                arr[i] = dummyArray[i] + arr[i - 1];

            System.out.print(arr[i] + " ");
        }

        System.out.println();

        return 0;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {20, 30, 25, 50};
        int n = arr.length;
        int dummyArray[] = new int[n + 1];

        buildArray(arr, dummyArray);

        update(dummyArray, 0, 1, 10);
        printArray(arr, dummyArray);
        update(dummyArray, 0, 2, 20);
        update(dummyArray, 2, 3, 30);

        printArray(arr, dummyArray);
    }
}
30 40 25 50
50 60 75 80

ការវិភាគស្មុគស្មាញ  

ស្មុគស្មាញពេលវេលា

O (q) ដែលជាកន្លែងដែល "Q" គឺជាចំនួនសំណួរព្រីនដែលប្រតិបត្តិជាសំណួរធ្វើបច្ចុប្បន្នភាព ឱ (១) ពេលវេលា។

សូម​មើល​ផង​ដែរ
Subarrays ដែលមានធាតុខុសគ្នា

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

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ចាប់តាំងពីយើងបានបង្កើតអារេភាពខុសគ្នាបន្ថែមយើងមានភាពស្មុគស្មាញនៃចន្លោះលីនេអ៊ែរ។