[LeetCode] 23. Merge k Sorted Lists

Codeing_ls 發(fā)布于2019-08-15 12:25 / 2723人閱讀

摘要：思路這題中的中，個(gè)還有其中個(gè)別的等于的情況，所以要判斷一下再加入代碼

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Heap

Time Complexity:
Update the heap costs O(nklogk)

Space Complexity:
O(kn)
The result listnode costs O(kn) and the heap is always O(k)

思路

Step1: Create a min heap with size k, loop through the input array of listnode and put all headnode into the heap
Step2: Create a new listnode two store the sorted list
Step3: Do the following steps k*n times (total number of the listnode)
(1) Pop out the min of the heap, add it to the result listnode
(2) If this listnode has next, insert it into the heap and update the heap

*這題中的input中，k個(gè)listnode還有其中個(gè)別的等于Null的情況，所以要判斷一下再加入minheap

代碼

public ListNode mergeKLists(ListNode[] lists) {
    if(lists == null || lists.length == 0) return null;
    ListNode dummy = new ListNode(0);
    ListNode head = dummy;
    PriorityQueue minHeap = new PriorityQueue<>(new Comparator(){
        public int compare(ListNode l1, ListNode l2){
            return l1.val - l2.val;
        }
    });
    
    for(int i = 0; i < lists.length; i++){
        if(lists[i] != null) minHeap.offer(lists[i]);
    }
    
    while(!minHeap.isEmpty()){
        ListNode min = minHeap.poll();
        head.next = min;
        head = head.next;
        if(min.next != null){
            minHeap.offer(min.next);
            min = min.next;
        }
    }
    return dummy.next;
}

云服務(wù)器 GPU云服務(wù)器 Lists Sorted LeetCode sorted-array

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/67930.html

相關(guān)文章

LeetCode 之 JavaScript 解答第23題 —— 合并K個(gè)有序鏈表（Merge K S

摘要：分治算法遞歸每層操作分解將原問題分解成一系列的子問題。分治算法滿足的條件可分解原問題與分解成的小問題具有相同的模式無關(guān)聯(lián)原問題分解成的子問題可以獨(dú)立求解，子問題之間沒有相關(guān)性，這一點(diǎn)是分治算法跟動(dòng)態(tài)規(guī)劃的明顯區(qū)別。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿題目：Merge K...

zhou_you 2019-08-23 16:53 評(píng)論0 收藏0
[Leetcode] Merge Two Sorted Lists Merge K Sorted L

摘要：注意因?yàn)槎阎惺擎湵砉?jié)點(diǎn)，我們?cè)诔跏蓟褧r(shí)還要新建一個(gè)的類。代碼初始化大小為的堆拿出堆頂元素將堆頂元素的下一個(gè)加入堆中 Merge Two Sorted Lists 最新更新請(qǐng)見：https://yanjia.me/zh/2019/01/... Merge two sorted linked lists and return it as a new list. The new list...

stefanieliang 2019-08-14 12:30 評(píng)論0 收藏0
23. Merge k Sorted Lists

摘要：題目合并排序鏈表并返回一個(gè)排序列表。分析和描述它的復(fù)雜性。直接對(duì)個(gè)鏈表合并，找到個(gè)鏈表頭最小的，將值追加到放在新創(chuàng)建的鏈表中，并把頭移到下一個(gè)節(jié)點(diǎn)，直到所有的鏈表頭運(yùn)行后發(fā)現(xiàn)超時(shí)嘗試兩兩合并兩個(gè)鏈表，知道最終合并成一個(gè)運(yùn)行通過題目 Merge k sorted linked lists and return it as one sorted list. Analyze and des...

qingshanli1988 2019-07-30 14:28 評(píng)論0 收藏0
355. Design Twitter , 用23. Merge k Sorted Lists和OO

摘要：的想法就是用每次得到最小的鏈表頭的值，輸出。每個(gè)都有一個(gè)關(guān)注人列表，用儲(chǔ)存。用戶可以發(fā)消息，關(guān)注別人，取消關(guān)注別人。可以系統(tǒng)得到關(guān)注人的消息合集，這個(gè)方法必須在這個(gè)層級(jí)。因?yàn)橛脩糁恢雷约旱男畔ⅰ? Merge k Sorted Lists /** * Definition for singly-linked list. * public class ListNode { * ...

1fe1se 2019-08-14 18:00 評(píng)論0 收藏0
leetcode 部分解答索引（持續(xù)更新～）

摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評(píng)論0 收藏0