本文共 2129 字,大约阅读时间需要 7 分钟。
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:[ 1->4->5, 1->3->4, 2->6]Output: 1->1->2->3->4->4->5->6
分析;
1. 分而治之。也就是把问题分解成两两合并直到全部合并成一个为止。时间复杂度O((m/2)(k/2 + k/4 + k/8 + …)logk),还是O(kmlogk),空间复杂度为O(1).
合并的时候可以像下图一样i和i+interval合并,也可以i和length-i合并。
分析i和i+interval合并: interval每次乘以2, 在一个循环内,两两合并的是lists[i]和lists[i+index](注意判断越界); 更新i=i+2*interval (这里一开始写成了i=i+interval+1然后就runtime error了。。)
两个链表合并的问题见Leetcode21,哪个链表当前元素小就将cur只想这个节点,并更新这个节点为下一个,需要注意用一个start保存一个初始节点,然后返回的是start.next.(这样可以避免为空的情况),还有每次cur = cur.next指向下一个。
public ListNode mergeKLists(ListNode[] lists) { if(lists==null || lists.length==0) return null; int len = lists.length; int interval = 1; while(intervall2.val){ cur.next = l2; l2 = l2.next; } else{ cur.next = l1; l1 = l1.next; } cur = cur.next; } if(l1!=null) cur.next = l1; if(l2!=null) cur.next = l2; return start.next; }
2. 使用PriorityQueue
用优先队列,每次插入元素都进行排序比较,最前面的元素小,所以需要new一个Comparator. 先把k个list的第一个元素放进heap,每次poll出一个后,放进poll出的那个的后一个,直到heap为空。时间复杂度O(mklogk),空间复杂度为O(k).
这里就需要清楚PriorityQueue的用法以及怎么使用匿名内部类:
(PriorityQueue)
(Java匿名类 还有内部类其他两种形式的介绍)
public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; if (lists.length == 1) return lists[0]; PriorityQueuequeue = new PriorityQueue<>(new Comparator () { public int compare(ListNode o1, ListNode o2) { return o1.val - o2.val; } }); for (int i = 0; i < lists.length; i++) { if (lists[i] != null) queue.add(lists[i]); } ListNode dummy = new ListNode(-1), cur = dummy; while (!queue.isEmpty()) { ListNode temp = queue.poll(); cur.next = temp; cur = temp; if (temp.next != null) queue.add(temp.next); } return dummy.next; }
参考
Heap与PriorityQueue的区别:
转载地址:http://anfni.baihongyu.com/