បញ្ចូលគ្នានូវបញ្ជីតម្រៀបឡេឡេលេខកូដពីរ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg សាលាមួយ Facebook ក្រុមហ៊ុន google ក្រុមហ៊ុន IBM ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle
បញ្ជីភ្ជាប់

បញ្ជីភ្ជាប់ គឺដូចជាអារេនៅក្នុងលក្ខណៈលីនេអ៊ែររបស់ពួកគេ។ យើងអាចបញ្ចូលគ្នានូវអារេដែលបានតម្រៀបពីរដើម្បីបង្កើតជាជួរដែលបានតម្រៀបជារួម។ នៅក្នុងបញ្ហានេះយើងត្រូវបញ្ចូលបញ្ជីដែលមានតំណភ្ជាប់ពីរប្រភេទ នៅ​ក្នុង​កន្លែង ដើម្បីត្រឡប់បញ្ជីថ្មីដែលមានធាតុនៃបញ្ជីទាំងពីរតាមរបៀបតម្រៀប។

ឧទាហរណ៍

បញ្ចូលគ្នានូវបញ្ជីតម្រៀបឡេឡេលេខកូដពីរ

L1 = 1   ->   2   ->   9
L2 = 1   ->   3   ->   4
1 1 2 3 4 9

វិធីសាស្រ្ត

វិធីសាមញ្ញបំផុតដើម្បីធ្វើវាគឺត្រូវប្រើឯកសារ ទ្រនិចពីរ បច្ចេកទេស។ បង្កើតបញ្ជីទទេថ្មី។ បន្ថែមធាតុតូចជាងមុនទាំងចង្អុលនិងបង្កើនទ្រនិចដែលត្រូវគ្នា។ នេះគឺជាវិធីសាស្រ្តល្អមួយប៉ុន្តែទាមទារអោយមានការបង្កើតបញ្ជីបន្ថែមដែលស៊ីកន្លែង។

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

ក្បួនដោះស្រាយ (វិធីសាស្ត្រណាតូ)

  1. បង្កើតមុខងារ បញ្ចូលគ្នានូវជួរពីរ () ដែលយកអ្នកចង្អុលបង្ហាញពីរជាអាគុយម៉ង់
  2. បើបញ្ជីមួយណាក៏បាន NULL, ត្រឡប់មួយទៀត
  3. បង្កើត បណ្ដោះអាសន្ន។ អថេរដែលនឹងចង្អុលទៅថ្នាំងតូចជាងក្នុងចំណោមក្បាលនៃបញ្ជីទាំងពីរ
  4. ឥឡូវនេះយ៉ាងហោចណាស់ថ្នាំងមួយត្រូវបានបន្ថែមទៅនឹងលទ្ធផលរបស់យើងដូច្នេះក្បាលមួយគួរតែត្រូវបានបង្កើន
  5. នេះបង្កើតជាគំរូរង។ ដូច្នេះសូមហៅមុខងារហៅដដែលៗហើយបន្ថែមវាទៅបណ្ដោះអាសន្ន
  6. ប្រសិនបើមាន List1.value <List2.value
    • temp = ListNode ថ្មី (List1.value) , temp-> បន្ទាប់ = បញ្ចូលបញ្ជីបញ្ចូលជួរ (បញ្ជី ១ -> បន្ទាប់បញ្ជី ២)
  7. បើ List2.value <= List1.value
    • temp = ListNode ថ្មី (List2.value) , temp-> បន្ទាប់ = បញ្ចូលតារាងបញ្ចូលជួរឈរ (បញ្ជីទី ១ បញ្ជី ២ - បន្ទាប់)
  8. ត្រឡប់ទៅវិញ បណ្ដោះអាសន្ន។ ដើម្បីទទួលបានបញ្ជីដែលចង់បាន

ក្បួនដោះស្រាយ (ប្រសើរបំផុត)

  1. បង្កើតទ្រនិចបញ្ជីថ្មីដែលនឹងត្រូវបានហៅ dummy_head ។
  2. រក្សា“ របស់ខ្លួនមុន” (ចំលងទ្រនិច) ដូច្នេះយើងអាចចូលមើលបញ្ជី ក្បាល អាសយដ្ឋាន។
  3. "ចង្អុលបន្ទាប់ក្បាល dummy គួរតែត្រូវបានរៀបចំតាមរបៀបដែលវាចង្អុលទៅថ្នាំងដែលបានកំណត់ជាមុននៅក្នុងបញ្ជី l1 និង l2.
  4. យើងអាចបំពេញភារកិច្ចខាងលើតាមវិធីដូចខាងក្រោមៈ
    • ធ្វើឱ្យបញ្ជីមានចំណុចឡើងវិញដោយចង្អុលបង្ហាញពីក្បាលរបស់ពួកគេ។
    • លើកលែងតែបញ្ជីមួយត្រូវបានផ្លាស់ប្តូរទាំងស្រុង៖
      • បន្ថែមថ្នាំងដែលមានតំលៃតូចជាងពីចំនុចចង្អុលពីរទៅបញ្ជីឈ្មោះ dummy_head, បង្កើនទ្រនិចដែលត្រូវគ្នា។
    • ឥឡូវយ៉ាងហោចណាស់ចំណុចមួយគឺ NULL ។ ដូច្នេះ, បន្ថែមខាងចុង មិនមែនជាមោឃៈ រាយបញ្ជីក្បាលអត់ចេះសោះ។
  5. ត្រឡប់ឯកសារ ក្បាល នៃបញ្ជីអត់ចេះសោះ។

ការអនុវត្តន៍

កម្មវិធី C ++ ដើម្បីបញ្ចូលបញ្ជីតម្រៀបពីរ

វិធីសាស្ត្រណាតូស

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

struct listNode
{
    int value;
    listNode* next;

    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
    if(!l1)
        return l2;
    if(!l2)
        return l1;

    listNode* temp;
    if(l1->value < l2->value)
    {
        temp = new listNode(l1->value);
        temp->next = mergeTwoSortedLists(l1->next , l2);
    }
    else
    {
        temp = new listNode(l2->value);
        temp->next = mergeTwoSortedLists(l1 , l2->next);
    }

    return temp;
}


void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


int main()
{
    listNode* l1 = new listNode(1);
    l1->next = new listNode(2);
    l1->next->next = new listNode(9);

    listNode* l2 = new listNode(1);
    l2->next = new listNode(3);
    l2->next->next = new listNode(4);

    print(mergeTwoSortedLists(l1 , l2));
    return 0;
}

វិធីសាស្ត្រល្អបំផុត

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

struct listNode
{
    int value;
    listNode* next;

    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};


listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
    listNode *dummy_head = new listNode(-1) , *prehead = dummy_head;
    while(l1 && l2)
    {
        if(l1->value < l2->value)
        {
            dummy_head->next = l1;
            l1 = l1->next;
        }
        else
        {
            dummy_head->next = l2;
            l2 = l2->next;
        }
        dummy_head = dummy_head->next;
    }

    dummy_head->next = (l1 ? l1 : l2);
    return prehead->next;
}



void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


int main()
{
    listNode* l1 = new listNode(1);
    l1->next = new listNode(2);
    l1->next->next = new listNode(9);

    listNode* l2 = new listNode(1);
    l2->next = new listNode(3);
    l2->next->next = new listNode(4);

    print(mergeTwoSortedLists(l1 , l2));
    return 0;
}
1 1 2 3 4 9

កម្មវិធីចាវ៉ាដើម្បីបញ្ចូលបញ្ជីតម្រៀបពីរ

វិធីសាស្ត្រណាតូស

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class merge_two_sorted_lists
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }


    public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
    {
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;

        listNode temp;
        if(l1.value < l2.value)
        {
            temp = new listNode(l1.value);
            temp.next = mergeTwoSortedLists(l1.next , l2);
        }
        else
        {
            temp = new listNode(l2.value);
            temp.next = mergeTwoSortedLists(l1 , l2.next);
        }

        return temp;
    }

    public static void main(String args[])
    {
        listNode l1 = new listNode(1);
        l1.next = new listNode(2);
        l1.next.next = new listNode(9);

        listNode l2 = new listNode(1);
        l2.next = new listNode(3);
        l2.next.next = new listNode(4);

        print(mergeTwoSortedLists(l1 , l2));
    }
}

វិធីសាស្ត្រល្អបំផុត

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class merge_two_sorted_lists
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }


    public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
    {
        listNode dummy_head = new listNode(-1) , prehead = dummy_head;
        while(l1 != null && l2 != null)
        {
            if(l1.value < l2.value)
            {
                dummy_head.next = l1;
                l1 = l1.next;
            }
            else
            {
                dummy_head.next = l2;
                l2 = l2.next;
            }
            dummy_head = dummy_head.next;
        }

        dummy_head.next = ((l1 != null) ? l1 : l2);
        return prehead.next;
    }

    public static void main(String args[])
    {
        listNode l1 = new listNode(1);
        l1.next = new listNode(2);
        l1.next.next = new listNode(9);

        listNode l2 = new listNode(1);
        l2.next = new listNode(3);
        l2.next.next = new listNode(4);

        print(mergeTwoSortedLists(l1 , l2));
    }
}
1 1 2 3 4 9

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

ស្មុគស្មាញពេលវេលា ដើម្បីបញ្ចូលបញ្ជីតម្រៀបពីរ

O (N + M), ដែលជាកន្លែងដែល N និង M គឺជាប្រវែងនៃបញ្ជីពីរ។ យើងឆ្លងកាត់បញ្ជីទាំងពីរម្តងក្នុងវិធីទាំងពីរដូច្នេះក្បួនដោះស្រាយទាំងពីរគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ ដើម្បីបញ្ចូលបញ្ជីតម្រៀបពីរ

នៅក្នុងវិធីសាស្រ្តល្អប្រសើរវាចាំបាច់ត្រូវយល់ថាមានតែយើងប៉ុណ្ណោះ រៀបចំចង្អុលបង្ហាញ។ ដូច្នេះទំហំថេរសម្រាប់គណនីអថេរសម្រាប់ការប្រើប្រាស់សតិ។ ដូច្នេះវិធីសាស្រ្តល្អបំផុតមានភាពស្មុគស្មាញនៃចន្លោះ ឱ (១). O (N + M) ចន្លោះត្រូវបានប្រើនៅក្នុងវិធីឆោតល្ងង់ដែលបានពិភាក្សា។