資訊專欄INFORMATION COLUMN
摘要：分治做法中，函數(shù)依然是將鏈表結(jié)點兩兩進行比較，然后在函數(shù)中迭代兩個二分后的結(jié)果。
Problem
Merge k sorted linked lists and return it as one sorted list.
Analyze and describe its complexity.
ExampleGiven lists:
[ 2->4->null, null, -1->null ],
return -1->2->4->null.
Note分治做法中，merge()函數(shù)依然是將鏈表結(jié)點兩兩進行比較，然后在sort()函數(shù)中迭代merge兩個二分后sort()的結(jié)果。PriorityQueue更為簡潔。
SolutionDivide & Conquer
public class Solution {
public ListNode mergeKLists(List lists) {
if (lists == null || lists.size() == 0) return null;
return sort(lists, 0, lists.size()-1);
}
public ListNode sort(List lists, int start, int end) {
if (start < end) {
int mid = (start+end)/2;
return merge(sort(lists, start, mid), sort(lists, mid+1, end));
}
return lists.get(start);
}
public ListNode merge(ListNode n1, ListNode n2) {
ListNode head = new ListNode(0);
ListNode cur = head;
while (n1 != null && n2 != null) {
if (n1.val < n2.val) {
cur.next = n1;
n1 = n1.next;
}
else {
cur.next = n2;
n2 = n2.next;
}
cur = cur.next;
}
if (n1 != null) cur.next = n1;
else cur.next = n2;
return head.next;
}
}
Priority Queue
Edited: 2018.3public class Solution {
public ListNode mergeKLists(List lists) {
if (lists == null || lists.size() == 0) return null;
ListNode dummy = new ListNode(0);
ListNode head = dummy;
PriorityQueue pq = new PriorityQueue (1, new Comparator (){
public int compare(ListNode n1, ListNode n2) {
return n1.val - n2.val;
}
});
for (int i = 0; i < lists.size(); i++) {
if (lists.get(i) != null) pq.offer(lists.get(i));
}
while (!pq.isEmpty()) {
head.next = pq.poll();
head = head.next;
//put the rest ListNode back to pq
if (head.next != null) pq.offer(head.next);
}
return dummy.next;
}
}
PriorityQueue Java 8
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue heap = new PriorityQueue<>((n1, n2) -> n1.val-n2.val);
for (ListNode n: lists) {
if (n != null) heap.offer(n);
}
ListNode head = new ListNode(0);
ListNode cur = head;
while (!heap.isEmpty()) {
cur.next = heap.poll();
cur = cur.next;
if (cur.next != null) heap.offer(cur.next);
}
return head.next;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/65838.html
摘要：先考慮和有無空集，有則返回另一個。新建鏈表，指針將和較小的放在鏈表頂端，然后向后遍歷，直到或之一為空。再將非空的鏈表放在后面。 Problem Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splici...
Problem Given two sorted integer arrays A and B, merge B into A as one sorted array. Notice You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements ...
摘要：循環(huán)里最好先考慮和其中之一已經(jīng)處理完的情況，就直接順序放另一個沒處理完的即可。然后再在里展開方法。避免其中一個數(shù)組較小會浪費效率的情況。丫把參數(shù)又換成了。。。 Problem Merge two given sorted integer array A and B into a new sorted integer array. Example A=[1,2,3,4] B=[2,4,5...
摘要：注意因為堆中是鏈表節(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...
摘要：思路這題中的中，個還有其中個別的等于的情況，所以要判斷一下再加入代碼 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 ...
閱讀 3762·2021-09-22 15:17
閱讀 1946·2021-09-22 14:59
閱讀 2346·2020-12-03 17:00
閱讀 3209·2019-08-30 15:55
閱讀 482·2019-08-30 11:23
閱讀 3487·2019-08-29 13:56
閱讀 518·2019-08-29 12:54
閱讀 2257·2019-08-29 12:49
