`
bcyy
  • 浏览: 1809684 次
文章分类
社区版块
存档分类
最新评论

Merge k Sorted Lists -- LeetCode

 
阅读更多
原题链接:http://oj.leetcode.com/problems/merge-k-sorted-lists/

这道题目在分布式系统中非常常见,来自不同client的sorted list要在central server上面merge起来。这个题目一般有两种做法,下面一一介绍并且分析复杂度。 第一种做法比较容易想到,就是有点类似于MergeSort的思路,就是分治法,不了解MergeSort的朋友,请参见归并排序-维基百科,是一个比较经典的O(nlogn)的排序算法,还是比较重要的。思路是先分成两个子任务,然后递归求子任务,最后回溯回来。这个题目也是这样,先把k个list分成两半,然后继续划分,知道剩下两个list就合并起来,合并时会用到Merge Two Sorted Lists这道题,不熟悉的朋友可以复习一下。代码如下:

public ListNode mergeKLists(ArrayList<ListNode> lists) {
    if(lists==null || lists.size()==0)
        return null;
    return helper(lists,0,lists.size()-1);
}
private ListNode helper(ArrayList<ListNode> lists, int l, int r)
{
    if(l<r)
    {
        int m = (l+r)/2;
        return merge(helper(lists,l,m),helper(lists,m+1,r));
    }
    return lists.get(l);
}
private ListNode merge(ListNode l1, ListNode l2)
{ 
    ListNode dummy = new ListNode(0);
    dummy.next = l1;
    ListNode cur = dummy;
    while(l1!=null && l2!=null)
    {
        if(l1.val<l2.val)
        {
            l1 = l1.next;
        }
        else
        {
            ListNode next = l2.next;
            cur.next = l2;
            l2.next = l1;
            l2 = next;
        }
        cur = cur.next;
    }
    if(l2!=null)
        cur.next = l2;
    return dummy.next;
}
我们来分析一下上述算法的时间复杂度。假设总共有k个list,每个list的最大长度是n,那么运行时间满足递推式T(k) = 2T(k/2)+O(n*k)。根据主定理,可以算出算法的总复杂度是O(nklogk)。如果不了解主定理的朋友,可以参见主定理-维基百科。空间复杂度的话是递归栈的大小O(logk)。
接下来我们来看第二种方法。这种方法用到了堆的数据结构,思路比较难想到,但是其实原理比较简单。维护一个大小为k的堆,每次去堆顶的最小元素放到结果中,然后读取该元素的下一个元素放入堆中,重新维护好。因为每个链表是有序的,每次又是去当前k个元素中最小的,所以当所有链表都读完时结束,这个时候所有元素按从小到大放在结果链表中。这个算法每个元素要读取一次,即是k*n次,然后每次读取元素要把新元素插入堆中要logk的复杂度,所以总时间复杂度是O(nklogk)。空间复杂度是堆的大小,即为O(k)。代码如下:

public ListNode mergeKLists(ArrayList<ListNode> lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(10,new Comparator<ListNode>(){
            @Override
            public int compare(ListNode n1, ListNode n2)
            {
                return n1.val-n2.val;
            }
        });
    for(int i=0;i<lists.size();i++)
    {
        ListNode node = lists.get(i); 
     if(node!=null)
     {
      heap.offer(node);
     }
    }
    ListNode head = null;
    ListNode pre = head;
    while(heap.size()>0)
    {
        ListNode cur = heap.poll();
        if(head == null)
        {
            head = cur;
            pre = head;
        }
        else
        {
            pre.next = cur;
        }
        pre = cur;
        if(cur.next!=null)
            heap.offer(cur.next);
    }
    return head;
}
可以看出两种方法有着同样的时间复杂度,都是可以接受的解法,但是却代表了两种不同的思路,数据结构也不用。个人觉得两种方法都掌握会比较好哈,因为在实际中比较有应用,所以也是比较常考的题目。

分享到:
评论

相关推荐

    LeetCode Merge 2 Sorted Lists解决方案

    LeetCode Merge 2 Sorted Lists解决方案

    leetcode中文版-LeetCode:力码

    leetcode中文版 LeetCode/Cpp 本人刷题记录在此,包含题意理解与算法思路,包含在Cpp文件内部注释,后续会持续更新。 有不懂的可以联系ji648513181,同时也欢迎志同道合O的朋友一起合作更新。 已更新剑指Offer答案...

    程序员面试宝典LeetCode刷题手册

    第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters ...23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli

    多线程leetcode-leetcode-java:leetcode上的题解,基于java语言

    多线程 leetcode 前言 每天刷点leetcode,基于java语言实现。 leetcode上难度分三档:easy,medium,hard. 如下: easy medium ...Merge k Sorted Lists Reverse Nodes in k-Group Trapping Rain Water

    leetcode答案-LeetCode-Trip:LeetCode刷题代码,大佬勿入

    LeetCode-Trip LeetCode刷题代码,大佬勿入。 为一年后的研究生找工作准备 目标是BAT的算法岗哈哈哈哈哈 争取做到每日一更 嗯…… 19.10.22:鸽了这么久,我又回来了……主要在实验室天天没啥事,过于佛系,刷刷题吧...

    lrucacheleetcode-leetcode-journal:记录所有LeetCode挑战的存储库

    lru缓存leetcode 力扣日记 欢迎来到我的 LeetCode 期刊库。 我的每个问题都将包括一个初始计划...k Sorted Lists (Hard) 31. Next Permutation (Medium) 34. Find First and Last Position of Element in Sorted Arr

    leetcode分类-leetcode:leetcode问题的代码

    leetcode 分类leetcode 问题分类 leetcode代码仓库,我的解题思路写在我的博客里: leetcode 代码库,我博客上的解题思路: mkdir 列表: 大批 #1:Two Sum #4:Median ...Sorted ...#23:Merge k Sorted Lists

    gasstationleetcode-leetcode-rust:莱特代码休息

    加油站 leetcode 力码锈 问题 # 标题 命令 1 cargo run --bin 1-two-sum 2 cargo run --bin 2-add-two-numbers 3 cargo run ...21-merge-two-sorted-lists 27 cargo run --bin 27-remove-element 28

    leetcode备忘录系统-Algorithms-DataStructures:算法-数据结构

    leetcode备忘录系统算法-数据结构 两个不错的排序算法及其 Big-O(完成) 归并排序 快速排序 冒泡排序 基本数据结构实现及其 Big-O 复杂性 哈希图 堆 队列 双端队列双端队列 链表 反转链表 合并两个排序列表 回文...

    leetcode中325题python-leetcode:leetcode

    merge-two-sorted-lists 82 删除排序链表中的重复元素 II remove-duplicates-from-sorted-list ii 83 删除排序链表中的重复元素 remove-duplicates-from-sorted-list 86 分隔链表 partition-list 92 反转链表 II ...

    leetcode2-Leetcode:Leetcode_answer

    leetcode 2 Leetcode答案集 关于项目: 本项目包含本人LeetCode解题的答案,全部将由JavaScript语言进行解答。并会在每个题目的文件夹中添加相关的思路解析。...Merge Two Sorted Lists JavaScript O(n)

    leetcode跳跃-leetcode:leetcode解题之路

    leetcode 跳跃 leetcode 按题型标签,记录...合并K个排序链表](./Heap/merge-k-sorted-lists.md) String 字符串 [0006 Z字形变换](./String/zigzag-conversion.md) [0030 串联所有单词的子串](./String/substring

    leetcode答案-LeetCode:Swift中的LeetCode

    Merge Two Sorted Lists Easy #26 Remove Duplicates from Sorted Array Easy #27 Remove Element Easy #35 Search Insert Position Easy #38 Count and Say Easy #53 Maximum Subarray Easy #66 Plus One Easy #70 ...

    lrucacheleetcode-leetcode:leetcode

    lru缓存leetcode leetcode ...Merge Two Sorted Lists 22. Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 3

    leetcode跳跃-leetcode:leetcode一天一次

    leetcode 跳跃 leetcode 动态规划,背包问题 01背包问题:416. Partition Equal Subset Sum 最长回文:5. Longest Palindromic ...Merge ...Sorted Lists 回文 双指针判断回文:680. 验证回文字符串 Ⅱ

    LeetCode最全代码

    26 | [Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/)| [C++](./C++/remove-duplicates-from-sorted-array.cpp) [Python](./Python/remove-duplicates...

    leetcode2sumc-LeetCode:LeetCode的一些题目

    Merge Two Sorted Lists 83 Easy Remove Duplicates from Sorted List 141 Easy Linked List Cycle 160 Easy Intersection of Two Linked Lists 203 Easy Remove Linked List Elements no 206 Easy Reverse Linked ...

    leetcode添加元素使和等于-leetcode:我的leetcode解决方案

    leetcode添加元素使和等于 经验教训 一定要吧功能尽量细化为函数,这样一者做题思路比较清晰,二者可以在某些情况下直接return值。 如果输入的形式是一个序列,则可以想想:分治、动规、贪婪,一般不建议搜索,因为...

    leetcode中文版-LeetCode:LeetcodeC++/Java

    leetcode中文版 LeetCode # Title Chinese Tag Solution 1 Two Sum 两数之和 array,hash 2 Add Two Numbers 两数相加 math 3 Longest Substring ...Sorted ...Merge Two Sorted Lists 合并两个有序链表 lin

    leetcode双人赛-LeetCode:力扣笔记

    leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 ...

Global site tag (gtag.js) - Google Analytics