Leetcode Solutions эки иреттелген тизмелерди бириктирүү


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon алма Bloomberg Capital One Facebook Гугл IBM Microsoft Oracle
Байланышкан тизме

Байланышкан тизмелер сызыктуу касиеттери боюнча массивдерге окшош. Жалпы иреттелген массивди түзүү үчүн эки иреттелген массивди бириктирсек болот. Бул көйгөйдө, биз эки иреттелген шилтеме тизмесин бириктиришибиз керек ордунда эки тизмектин элементтерин иреттелген түрдө камтыган жаңы тизмени кайтаруу.

мисал

Leetcode Solutions эки иреттелген тизмелерди бириктирүү

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

жакындоо

Муну жасоонун эң жөнөкөй жолу - эки көрсөткүч техника. Жаңы бош тизме түзүңүз. Кичинекей элементтерди эки көрсөткүчтүн арасына кошуп, тиешелүү көрсөткүчтү көбөйтүңүз. Бул жакшы ыкма, бирок орун талап кылган кошумча тизме түзүүнү талап кылат.

Оптималдуу мамиле бир гана убакытты жүргүзүү үчүн туруктуу мейкиндикти колдонушу керек ордунда сорттоо. Биз кайталанма ыкманы колдонсок болот. Эки тизмеде тең мурунтан эле сакталган түйүндөр бар. Жаңы тизме көрсөткүчүн жана андан кийинки “түзүүкийинки көрсөткүчтөр”Эс тутумундагы алдын-ала аныкталган түйүндөрдү көрсөтүшү керек. Бул процессте биз түзөбүз жок жаңы түйүндөр.

Алгоритм (Наивдик ыкма)

  1. Функцияны түзүү mergeTwoSortedLists () аргумент катары эки тизме көрсөткүчүн алат
  2. Эгерде тизмелердин бири болсо НӨЛ, экинчисин кайтар
  3. түзүү темп эки тизмектин башындагы кичинекей түйүндү көрсөтүүчү өзгөрмө
  4. Эми, жок дегенде, биздин жыйынтыкка бир түйүн тиркелет, андыктан бир башты көбөйтүү керек
  5. Бул субпроблеманы жаратат. Ошентип, ошол эле рекурсивдик функцияны чакырып, аны темпке кошуңуз
  6. Эгерде List1.value <List2.value
    • темп = жаңы ListNode (List1.value) , temp-> next = mergeTwoSortedLists (List1-> кийинки, List2)
  7. Эгерде List2.value <= List1.value
    • темп = жаңы ListNode (List2.value) , temp-> next = mergeTwoSortedLists (List1, List2-> кийинки)
  8. Return темп керектүү тизмени алуу үчүн

Алгоритм (Оптималдуу)

  1. Деп аталган жаңы тизме көрсөткүчүн түзүңүз dummy_head.
  2. prehead”(Көчүрмө көрсөткүч), биз тизмеге кире алабыз баш дареги.
  3. "кийинки көрсөткүчтөр”Dummy_head тизменин алдын-ала аныкталган түйүндөрүн көрсөтүп тургандай кылып иштетүү керек l1 жана l2.
  4. Жогорудагы тапшырманы төмөнкү жолдор менен аткара алабыз:
    • Тизмелерди башынан баштап көрсөткүчтөр менен кайталай бериңиз.
    • Эгерде тизмелердин бири толугу менен өтпөсө:
      • Эки тизме көрсөткүчүнөн кичине бааланган түйүндү тиркеп коюңуз dummy_head, тиешелүү көрсөткүчтү көбөйтүү.
    • Эми көрсөткүчтөрдүн жок дегенде бири НӨЛ. Ошентип, тиркөө нөл эмес тизме муляждын башына.
  5. Return the баш муляж тизмесинин.

ишке ашыруу

Эки иреттелген тизмени бириктирүү үчүн C ++ программасы

Naive Appocach

#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 программасы

Naive Appocach

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 (1). O (N + M) мейкиндик талкууланган жөнөкөй мамиле колдонулат.