Ду рӯйхати ҳалшудаи Leetcode Solutions -ро якҷоя кунед


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe Amazon себ Блумберг Пойтахт Яке аз Facebook Google IBM Microsoft Oracle
Рӯйхати алоқаманд

Рӯйхати алоқаманд аз ҷиҳати хосияти хаттиашон ба массив шабеҳанд. Мо метавонем ду массиви ҷудошударо якҷоя карда, массиви умумии мураттаб созем. Дар ин масъала, мо бояд ду рӯйхати алоқамандро муттаҳид кунем дар ҷои баргардонидани рӯйхати нав, ки унсурҳои ҳарду рӯйхатро ба тарзи мураттаб дар бар мегирад.

мисол

Ду рӯйхати ҳалшудаи Leetcode Solutions -ро якҷоя кунед

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
    • temp = ListNode нав (List1.value) , temp-> оянда = mergeTwoSortedLists (List1-> next, List2)
  7. Агар List2.value <= List1.value
    • temp = ListNode нав (List2.value) , temp-> оянда = mergeTwoSortedLists (List1, List2-> next)
  8. бозгашт temp барои ба даст овардани рӯйхати дилхоҳ

Алгоритм (беҳтарин)

  1. Нишондиҳандаи рӯйхати навро эҷод кунед, ки номида мешавад саргум.
  2. Нигоҳ доштани “онпешг"(Нишонаи нусхабардорӣ), то ки мо ба рӯйхат дастрасӣ пайдо кунем сарлавҳа суроға.
  3. Дар "нишоннамои оянда”-И dummy_head бояд тавре идора карда шавад, ки он ба гиреҳҳои пешакӣ муайяншуда дар рӯйхатҳо ишора кунад l1 ва l2.
  4. Мо вазифаи дар боло зикршударо бо роҳҳои зерин иҷро карда метавонем:
    • Такрори рӯйхатҳоро бо нишондиҳандаҳо аз сарашон сар кунед.
    • Магар яке аз рӯйхатҳо пурра гузарад:
      • Гиреҳи арзонтарро аз ду нишоннамои рӯйхат ба dummy_head, афзоиши нишоннамои мувофиқ.
    • Ҳоло, ҳадди аққал як нишондиҳанда ин аст НОЛЛ. Пас, замима кунед бефоида рӯйхат ба сари фиребанда.
  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 дарозии ду рӯйхат мебошанд. Мо ҳарду рӯйхатро дар ҳарду равиш як маротиба убур мекунем, аз ин рӯ ҳарду алгоритм хатӣ мебошанд.

Мураккабии фазо Барои якҷоя кардани ду рӯйхати мураттаб

Дар равиши оптималӣ, фаҳмидан муҳим аст, ки мо танҳо нишондиҳандаҳоро идора кунед. Ҳамин тавр, фазои доимӣ барои тағирёбандаҳо истифодаи хотираро ҳисоб мекунанд. Аз ин рӯ, усули оптималӣ дорои мураккабии фазоии О (1). O (N + M) фазо дар усули соддалавҳонаи мавриди баррасӣ истифода мешавад.