ច្របាច់បញ្ចូលជួរអារេឡេសសូលូសិន  


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg ByteDance ស៊ីស្កូ របស់ eBay Expedia Facebook ក្រុមហ៊ុន Goldman Sachs ក្រុមហ៊ុន google ក្រុមហ៊ុន IBM LinkedIn lyft ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Netflix Inc ក្រុមហ៊ុន Oracle តារាង Uber VMware ក្រុមហ៊ុន Yahoo Yandex
ក្បួនដោះស្រាយ អារេ ការសរសេរកូដ សំភាសន៍ កិច្ចសម្ភាសន៍ LeetCode LeetCodeSolutions ទ្រនិចពីរ

នៅក្នុងបញ្ហា“ ការបញ្ចូលគ្នាជួរអារេ” យើងត្រូវបានផ្តល់ពីរ អារេ តម្រៀបតាមលំដាប់មិនមែនលំដាប់។ អារេទីមួយមិនត្រូវបានបំពេញយ៉ាងពេញលេញនិងមានកន្លែងទំនេរគ្រប់គ្រាន់ដើម្បីផ្ទុកធាតុទាំងអស់នៃអារេទី XNUMX ផងដែរ។ យើងត្រូវបញ្ចូលគ្នានូវអារេទាំងពីរដូចជាអារេទីមួយមានធាតុនៃអារេទាំងពីរហើយត្រូវបានតម្រៀបតាម មិនចុះ លំដាប់។

ឧទាហរណ៍  

{1 , 2 , 3 , - , - , -}
{2 , 6 , 7}
1 2 2 3 6 7
{1 , 1 , 1 ,  - , -}
{2 , 4}
1 1 1 2 4

វិធីសាស្រ្ត (តម្រៀប)  

យើងអាចផ្ទេរធាតុទាំងអស់នៃអារេទី ២ ទៅធាតុទីមួយ។ បន្ទាប់មកយើងអាចតម្រៀបជួរទីមួយដើម្បីទទួលបានលទ្ធផលដែលត្រូវការ។

ក្បួនដោះស្រាយ

  1. សម្រាប់ i = 0 ដល់ i = N, ចាត់តាំង
    1. a [i + m] = b [i], a = អារេដំបូង, ខ = អារេទី ២
  2. តម្រៀបអារេដំបូង
  3. បោះពុម្ពលទ្ធផលដែលត្រូវការ

ការអនុវត្តដំណោះស្រាយបញ្ចូលគ្នាអារេ Leetcode

កម្មវិធី C ++

#include <bits/stdc++.h>
using namespace std;

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    for(int i = 0 ; i < n ; i++)
        a[i + m] = b[i];

    sort(a.begin() , a.end());
    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

កម្មវិធីចាវ៉ា

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        for(int i = 0 ; i < n ; i++)
            a[i + m] = b[i];
        Arrays.sort(a);
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

ការវិភាគស្មុគស្មាញនៃដំណោះស្រាយបញ្ចូលគ្នាអារេ Leetcode

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

O (KlogK), ដែលជាកន្លែងដែល K = N + M។ N = ទំហំនៃអារេទី ១, M = ទំហំនៃអារេទី ២ ។ ដូចដែលយើងតម្រៀបជួរទីមួយបន្ទាប់ពីវាបានរក្សាទុកធាតុ N + M ទាំងអស់។

សូម​មើល​ផង​ដែរ
ការបង្កើនដំណោះស្រាយឡេឡេកូដកូដកាន់តែថយចុះ

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

ឱ (១) ដោយសារតែការចងចាំថេរត្រូវបានប្រើសម្រាប់អថេរ។

វិធីសាស្រ្ត (ចំណុចពីរ)  

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

នេះនឹងកាត់បន្ថយបញ្ហានៃ“ ការចងចាំអារេបន្ថែម” នៅពេលយើងបន្តជួសជុលធាតុនៅក្នុងចន្លោះទំនេរ។

ច្របាច់បញ្ចូលជួរអារេឡេសសូលូសិនពិន

ក្បួនដោះស្រាយ

  1. ចាប់ផ្តើមអថេរពីរ i និង j រក្សាសន្ទស្សន៍នៃធាតុចុងក្រោយនៃអារេទីមួយនិងទីពីររៀងៗខ្លួន។
    • i = M - 1, j = N - 1
  2. ចាប់ផ្តើមអថេរ idxដោយរក្សាទុកសន្ទស្សន៍ចុងក្រោយនៃអារេដំបូងគឺ៖
    • idx = N + M - ១
  3. ឥឡូវធ្វើដូចខាងក្រោមរហូតដល់ណាមួយ i or j ក្លាយជាលេខសូន្យ
    • បើ a [ខ្ញុំ]> = ខ [ច]
      • ចាត់តាំង [idx] = a [i], ការថយចុះ i
    • ផ្សេងទៀត
      • ចាត់តាំង [idx] = b [j], បន្ថយ j
    • ការថយចុះ idx
  4. ទាំង ខ្ញុំឬច មិនមែនសូន្យដែលមានន័យថាធាតុមួយចំនួនមិនទាន់ត្រូវបានបញ្ចូលគ្នា។ ដូចដែលពួកគេនឹងមានលក្ខណៈតម្រៀបរួចហើយយើងគ្រាន់តែបន្ថែមពួកវាទៅជួរទីមួយនៅខាងមុខ។
  5. ខណៈពេល i មិនបានក្លាយជាសូន្យ,
    1. ចាត់តាំង [idx] = a [i]
    2. ការថយចុះ idx និង i
  6. ខណៈពេល j មិនបានក្លាយជាសូន្យ,
    1. ចាត់តាំង [idx] = b [j]
    2. ការថយចុះ idx និង j
  7. ឥឡូវនេះអារេដំបូងមានធាតុទាំងអស់តាមលំដាប់លំដោយដែលត្រូវការ។

ការអនុវត្តដំណោះស្រាយបញ្ចូលគ្នាអារេ Leetcode

កម្មវិធី C ++

#include <bits/stdc++.h>
using namespace std;

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    int i = m - 1 , j = n - 1 , idx = m + n - 1;
    while(i >= 0 && j >= 0)
    {
        if(a[i] >= b[j])
        {
            a[idx] = a[i];
            i--;
        }
        else
        {
            a[idx] = b[j];
            j--;
        }
        idx--;
    }


    while(i >= 0)
        a[idx--] = a[i--];

    while(j >= 0)
        a[idx--] = b[j--];

    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

កម្មវិធីចាវ៉ា

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        int i = m - 1 , j = n - 1 , idx = m + n - 1;
        while(i >= 0 && j >= 0)
        {
            if(a[i] >= b[j])
            {
                a[idx] = a[i];
                i--;
            }
            else
            {
                a[idx] = b[j];
                j--;
            }
            idx--;
        }

        while(i >= 0)
            a[idx--] = a[i--];

        while(j >= 0)
            a[idx--] = b[j--];

        return;
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

ការវិភាគស្មុគស្មាញនៃដំណោះស្រាយបញ្ចូលគ្នាអារេ Leetcode

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

O (N + M). N = ទំហំនៃអារេដំបូង M = ទំហំនៃអារេទី ២ ។ នៅពេលយើងឆ្លងកាត់អារេទាំងពីរម្តង។

សូម​មើល​ផង​ដែរ
ថាមពលនៃដំណោះស្រាយឡេឡេលេខកូដបួន

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

ឱ (១), ដូចដែលយើងផ្ទុកធាតុទាំងអស់ក្នុងជួរទីមួយ។ ដូច្នេះក្បួនដោះស្រាយគឺ នៅ​ក្នុង​កន្លែង.