[LeetCode] 23. Merge k Sorted Lists

Codeing_ls 发布于2019-08-15 12:25 / 2577人阅读

摘要：思路这题中的中，个还有其中个别的等于的情况，所以要判断一下再加入代码

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;
}

超融合服务器专线服务 Lists Sorted LeetCode sorted-array

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67930.html

LeetCode 之 JavaScript 解答第23题 —— 合并K个有序链表（Merge K S

摘要：分治算法递归每层操作分解将原问题分解成一系列的子问题。分治算法满足的条件可分解原问题与分解成的小问题具有相同的模式无关联原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别。 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

摘要：注意因为堆中是链表节点，我们在初始化堆时还要新建一个的类。代码初始化大小为的堆拿出堆顶元素将堆顶元素的下一个加入堆中 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

摘要：题目合并排序链表并返回一个排序列表。分析和描述它的复杂性。直接对个链表合并，找到个链表头最小的，将值追加到放在新创建的链表中，并把头移到下一个节点，直到所有的链表头运行后发现超时尝试两两合并两个链表，知道最终合并成一个运行通过题目 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

摘要：的想法就是用每次得到最小的链表头的值，输出。每个都有一个关注人列表，用储存。用户可以发消息，关注别人，取消关注别人。可以系统得到关注人的消息合集，这个方法必须在这个层级。因为用户只知道自己的信息。 Merge k Sorted Lists /** * Definition for singly-linked list. * public class ListNode { * ...

1fe1se 2019-08-14 18:00 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0