[LeetCode] 23. Merge k Sorted Lists

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

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

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個listnode還有其中個別的等于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;
}

云服務器 GPU云服務器 Lists Sorted LeetCode sorted-array

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67930.html

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

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

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

摘要：注意因為堆中是鏈表節(jié)點，我們在初始化堆時還要新建一個的類。代碼初始化大小為的堆拿出堆頂元素將堆頂元素的下一個加入堆中 Merge Two Sorted Lists 最新更新請見：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 評論0 收藏0
23. Merge k Sorted Lists

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

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

摘要：的想法就是用每次得到最小的鏈表頭的值，輸出。每個都有一個關注人列表，用儲存。用戶可以發(fā)消息，關注別人，取消關注別人。可以系統(tǒng)得到關注人的消息合集，這個方法必須在這個層級。因為用戶只知道自己的信息。 Merge k Sorted Lists /** * Definition for singly-linked list. * public class ListNode { * ...

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

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

leo108 2019-08-15 14:26 評論0 收藏0