Leetcode Solutions гэсэн хоёр эрэмбэлэгдсэн жагсаалтыг нэгтгэх  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Apple-ийн Bloomberg Капитал Нэг Facebook-ийн Google-ийн IBM Microsoft- Oracle-ийн
алгоритмууд кодлох ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions Холбогдсон жагсаалт

Холбоотой жагсаалтууд нь шугаман шинж чанараараа массивтай төстэй юм. Бид хоёр эрэмбэлэгдсэн массивыг нэгтгэж ерөнхий эрэмбэлэгдсэн массив үүсгэх боломжтой. Энэ асуудалд бид хоёр эрэмбэлэгдсэн холбосон жагсаалтыг нэгтгэх ёстой газар дээр нь хоёр жагсаалтын элементүүдийг агуулсан шинэ жагсаалтыг эрэмбэлсэн байдлаар буцаах.

Жишээ нь  

Leetcode Solutions гэсэн хоёр эрэмбэлэгдсэн жагсаалтыг нэгтгэхPin

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

арга барил  

Үүнийг хийх хамгийн энгийн арга бол хоёр заагч техник. Шинэ хоосон жагсаалт үүсгэх. Бага элементүүдийг заагч хоёуланг нь хавсаргаад харгалзах заагчийг өсгө. Энэ бол сайн арга боловч орон зай зарцуулдаг нэмэлт жагсаалт гаргахыг шаарддаг.

Оновчтой арга нь зөвхөн хийхийн тулд тогтмол орон зайг ашиглах ёстой байрандаа ангилах. Бид давталтын аргыг баримталж болно. Жагсаалтанд хоёуланд нь аль хэдийн хадгалагдсан зангилаа байна. Шинэ жагсаалтын заагчийг үүсгээд дараачийн “дараагийн заагч"Санах ойд урьдчилан тодорхойлсон зангилаа руу чиглүүлэх ёстой. Энэ процесст бид бий болгодог Үгүй шинэ зангилаа.

Алгоритм (гэнэн хандлага)  

  1. Функц үүсгэх mergeTwoSortedLists () Энэ нь жагсаалтын хоёр заагчийг аргумент болгон авдаг
  2. Хэрэв жагсаалтын аль нэг нь байвал ҮГҮЙ, нөгөөг нь буцаа
  3. Бүтээх temp хоёр жагсаалтын толгойн хоорондох жижиг зангилааг зааж өгөх хувьсагч
  4. Одоо бидний үр дүнд дор хаяж нэг зангилаа хавсаргасан тул нэг толгойг нэмэгдүүлэх хэрэгтэй
  5. Энэ нь дэд асуудал үүсгэдэг. Тиймээс, ижил рекурсив функцийг дуудаж temp дээр нэмнэ үү
  6. Хэрэв List1.value <List2.value
    • түр зуур = шинэ ListNode (List1.value) , temp-> next = mergeTwoSortedLists (List1-> next, List2)
  7. Хэрэв List2.value <= List1.value
    • түр зуур = шинэ ListNode (List2.value) , temp-> next = mergeTwoSortedLists (List1, List2-> next)
  8. буцах temp хүссэн жагсаалтыг авах
мөн үзнэ үү
Leetcode шийдлийг интервал оруулах

Алгоритм (Оновчтой)  

  1. Дуудагдах шинэ жагсаалтын заагчийг үүсгээрэй дамми_ толгой.
  2. “Хадгалахтолгой"(Заагчийг хуулах). Ингэснээр бид жагсаалтад хандах боломжтой болно толгой хаяг.
  3. "дараагийн заагч”Dummy_head-ийг жагсаалтад байгаа урьдчилан тодорхойлсон зангилаа руу чиглүүлж байх ёстой l1 болон l2.
  4. Бид дээрх даалгаврыг дараахь байдлаар хийж болно.
    • Толгойноос нь эхлээд заагчаар жагсаалтыг давтаж байгаарай.
    • Жагсаалтын аль нэгийг бүрэн гүйцэд туулахгүй бол:
      • Жагсаалтын хоёр заагчаас бага утгатай зангилаа руу дамми_ толгой, харгалзах заагчийг нэмэгдүүлэх.
    • Одоо нэг заагч нь дор хаяж нэг юм ҮГҮЙ. Тиймээс хавсаргана уу тэг биш дамми толгой руу жагсаах.
  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

Хоёр эрэмбэлэгдсэн жагсаалтыг нэгтгэх Java програм

Гэнэн хандлага

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 нь хоёр жагсаалтын урт юм. Бид жагсаалтын аль алиныг нь хоёуланд нь хоёуланд нь нэг удаа тойрч гардаг тул алгоритмууд хоёулаа шугаман байна.

мөн үзнэ үү
Хүчин төгөлдөр төгс квадрат Leetcode шийдэл

Сансрын нарийн төвөгтэй байдал Хоёр эрэмбэлэгдсэн жагсаалтыг нэгтгэх

Оптимал хандлагын хувьд бид зөвхөн гэдгийг л ойлгох нь чухал юм заагчийг удирдах. Тэгэхээр хувьсагчдын тогтмол зай нь санах ойн хэрэглээг тооцдог. Тиймээс оновчтой арга нь орон зайн нарийн төвөгтэй байдаг O (1). O (N + M) орон зайг хэлэлцсэн гэнэн хандлагад ашигладаг.