K сұрыпталған байланыстырылған тізімдерді біріктіру  


Күрделілік дәрежесі қиын
Жиі кіреді Adobe Amazon алма Bloomberg ByteDance Мәліметтер базасы еВау Facebook Голдман Сакс Microsoft Oracle Palantir Technologies Twitter қиятын тілек
Бөліңіз және жеңіңіз Үйінді Байланыстырылған тізім

Біріктіру K сұрыпталды байланыстырылған тізімдер мәселе сұхбат тұрғысынан өте танымал. Бұл сұрақ Google, Microsoft, Amazon және т.б. сияқты ірі компанияларда бірнеше рет қойылады. Атауынан көрініп тұрғандай, бізге сұрыпталған тізімдер берілген. Біз оларды а-ға біріктіруіміз керек Бірыңғай сұрыпталған тізбе.

Мұны жақсы түсіну үшін сынақ ісінің үлгісін қарастырайық:

мысал  

енгізу

[

1-> 2-> 3,

1-> 4-> 6,

2-> 3

]

шығыс

1->1->2->2->3->3->4->6

Merge K сұрыпталған байланыстырылған тізімдерге арналған тәсіл-1  

Брут күші 

  • Барлық байланыстырылған тізімдерді айналып өтіп, барлық мәндерді Array / ArrayList / Vector ішіне салыңыз (қандай сақтау орны сізге ыңғайлы болса)
  • Деректерді сұрыптау
  • Сұрыпталған деректерден жаңа сілтеме тізімін жасаңыз

Воила! Біздің біріктірілген және сұрыпталған байланыстырылған тізім дайын. Мұны код арқылы жақсы түсінейік.

Java бағдарламасы

class Solution 
{
    public ListNode mergeKLists(ListNode[] lists) 
    {
        ListNode aux=new ListNode(0);
        List<Integer>lisa=new ArrayList<Integer>();
        for(int i=0;i<lists.length;i++)
        {
            ListNode ptr=lists[i];
            while(ptr!=null)
            {
                lisa.add(ptr.val);
                ptr=ptr.next;
            }
        }
        Collections.sort(lisa);
        ListNode ptr=aux;
        for(int i=0;i<lisa.size();i++)
        {
            ListNode temp=new ListNode(lisa.get(i));
            temp.next=null;
            ptr.next=temp;
            ptr=ptr.next;
        }
        return aux.next;
    }
}

C ++ бағдарламасы

class Solution 
{
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
    vector<int>store;
    for(int i=0;i<lists.size();i++)
        {
            ListNode *ptr=lists[i];
            while(ptr!=NULL)
            {
                store.push_back(ptr->val);
                ptr=ptr->next;
            }
        }
        sort(store.begin(),store.end());
        ListNode *ptr=new ListNode();
        ListNode *aux=ptr;
        for(int i=0;i<store.size();i++)
        {
            ListNode *temp=new ListNode(store[i]);
            temp->next=NULL;
            ptr->next=temp;
            ptr=ptr->next;
        }
        return aux->next;
    }
};
[

1->2->3,

1->4->6,

2->3

]
1->1->2->2->3->3->4->6

Күрделілікті талдау

Енді жоғарыдағы шешімнің уақыттағы күрделілігін қарастырайық:

Сондай-ақ, қараңыз
Екі Байланыстырылған Тізімнің қиылысу нүктесін алу үшін функция жазыңыз

Қозғалыс пен жаратылыстың уақыты: O (n)

Сұрыптауға уақыт кетеді: O (n log n)

Уақытты күрделендіру: O (n log n)

Merge K сұрыпталған байланыстырылған тізімдерге арналған тәсіл-2  

Min-Heap пайдалану

Басым кезегін сақтау орны ретінде пайдалануға болады

артықшылықтары:

  • Сұрыптаудың қажеті жоқ

Кодтың көмегімен осыны қарастырайық

Java бағдарламасы

class Solution 
{
    public ListNode mergeKLists(ListNode[] lists)
    {
    Queue<Integer>store=new PriorityQueue();
    for(int i=0;i<lists.length;i++)
    {
        ListNode ptr=lists[i];
        while(ptr!=null)
        {
            store.add(ptr.val);
            ptr=ptr.next;
        }
    }
    if(store.isEmpty() )    
        return null;
    ListNode head=new ListNode(store.poll());
    ListNode cur=head;
    while(!store.isEmpty())
    {
        ListNode temp=new ListNode(store.poll());
        cur.next=temp;
        cur=cur.next;
    }
    return head;
    }
}
[
2->5->7->9,
1->2->3->->10
]
1->2->2->3->5->7->9->10

Күрделілікті талдау

Жоғарыда айтылғандардың уақыт күрделілігі: O (n log n)

Merge K сұрыпталған байланыстырылған тізімдерге арналған тәсіл-3  

Бөліңіз және жеңіңіз

  • Бөлу қадамы

Мақсаты-К / 2 функциясын бір уақытта біріктіру үшін k тізімдерін жібереді

  • Біріктіру қадамы

МАҚСАТЫ -Кішірек мәндерді қарастыру және оларды жаңа тізім жасау үшін қосу

    • Біріктірілген тізімді қайтару үшін нұсқағыш жасаңыз
    • Екі тізімнен де кішірек мән қосыңыз
    • Мән алынған өсу көрсеткіші
    • Екі тізімнен біріктірілген және сұрыпталған тізімді қайтару
K сұрыпталған байланыстырылған тізімдерді біріктірутүйреуіш
Бірнеше тізімге біріктіруді көрсету

Кодтың көмегімен мұны жақсы түсінейік

Java бағдарламасы

class Solution 
{
    public static ListNode merge(ListNode l1,ListNode l2)
    {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        ListNode aux=new ListNode();
        ListNode head=aux;
        while(l1!=null && l2!=null)
        {
            if(l1.val>l2.val)
            {
                aux.next=l2;
                l2=l2.next;
            }
            else 
            {
                aux.next=l1;
                l1=l1.next;
            }
            aux=aux.next;
        }
        if(l1!=null)
            aux.next=l1;
        else if(l2!=null)
            aux.next=l2;
        return head.next;
    }
    public static ListNode divide(ListNode[]lists,int start,int end)
    {
        if(end<start)
            return null;
        if(end==start)
            return lists[start];
        int mid=start+(end-start)/2;
        return(merge(divide(lists,start,mid),divide(lists,mid+1,end)));
    }
    public ListNode mergeKLists(ListNode[] lists)
    {
     if(lists == null) 
         return null;
     if(lists.length == 1) 
         return lists[0];
     return divide(lists,0,lists.length-1);   
    }
}

C ++ бағдарламасы

class Solution 
{
  public:
    ListNode* merge(ListNode *l1,ListNode *l2)
    {
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        ListNode *aux=new ListNode();
        ListNode *head=aux;
        while(l1!=NULL && l2!=NULL)
        {
            if(l1->val>l2->val)
            {
                aux->next=l2;
                l2=l2->next;
            }
            else 
            {
                aux->next=l1;
                l1=l1->next;
            }
            aux=aux->next;
        }
        if(l1!=NULL)
            aux->next=l1;
        else if(l2!=NULL)
            aux->next=l2;
        return head->next;
    }
    public:
    ListNode* divide(vector<ListNode*>&lists,int start,int end)
    {
        if(end<start)
            return NULL;
        if(end==start)
            return lists[start];
        int mid=start+(end-start)/2;
        return(merge(divide(lists,start,mid),divide(lists,mid+1,end)));
    }
    public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
     if(lists.size() == 0) 
         return NULL;
     if(lists.size() == 1) 
         return lists[0];
     return divide(lists,0,lists.size()-1);   
    }
};
[
1->2,
3,
4->5->6->7,
8->9->10,
11
]
1->2->3->4->5->6->7->8->9->10->11

Күрделілікті талдау

Уақыт күрделілігі = O (n log n)

Сондай-ақ, қараңыз
Bellman Форд Алгоритмі

Кеңістіктің күрделілігі = O (1)

Әдебиеттер тізімі