问题:
在O(N lgK) 时间内合并K个有序链表, 这里N指的是K个链表中所有的元素个数。
分析:
这是一道非常经典的面试题,在很多大公司的面试题中,此题频繁出现。这题也是算法导论的作业题。
这题的思路如下:
1) 在每一个链表中取出第一个值,然后把它们放在一个大小为K的数组里,然后把这个数组当成heap,然后把该堆建成最小堆。此步骤的时间复杂度为O(K)
2 )取出堆中的最小值(也是数组的第一个值),然后把该最小值所处的链表的下一个值放在数组的第一个位置。如果链表中有一个已经为空(元素已经都被取出),则改变heap的大小。然后,执行MIN-HEAPIFY操作,此步骤的时间复杂度为O(lg K).
3 ) 不断的重复步骤二,直到所有的链表都为空。
代码如下:
-
class ListNode {
-
int val;
-
ListNode next;
-
ListNode(int x) {
-
val = x;
-
next = null;
-
}
-
}
-
-
public class Solution {
-
public static void main(String[] args) {
-
-
ListNode n1 = new ListNode(1);
-
ListNode n7 = new ListNode(2);
-
ListNode n9 = new ListNode(2);
-
ListNode n2 = new ListNode(1);
-
ListNode n4 = new ListNode(1);
-
ListNode n8 = new ListNode(2);
-
-
ArrayList<ListNode> lists = new ArrayList<ListNode>();
-
n1.next = n7;
-
n7.next = n9;
-
n2.next = n4;
-
n4.next = n8;
-
-
lists.add(n1);
-
lists.add(n2);
-
-
Solution test = new Solution();
-
ListNode head = test.mergeKLists(lists);
-
while(head != null) {
-
System.out.println(head.val);
-
head = head.next;
-
}
-
}
-
-
public ListNode mergeKLists(ArrayList<ListNode> lists) {
-
ArrayList<ListNode> heap = new ArrayList<ListNode>();
-
for (int i = 0; i < lists.size(); i++) {
-
if (lists.get(i) != null) {
-
heap.add(lists.get(i));
-
}
-
}
-
-
ListNode head = null;
-
ListNode current = null;
-
if (heap.size() == 0) return null;
-
minHeapify(heap);
-
while (heap.size() != 0) {
-
if (head == null) {
-
head = heap.get(0);
-
current = heap.get(0);
-
} else {
-
current.next = heap.get(0);
-
current = current.next;
-
}
-
-
if (current.next != null) {
-
heap.set(0, current.next);
-
heapify(heap, 0);
-
} else {
-
heap.remove(0);
-
minHeapify(heap);
-
}
-
}
-
return head;
-
}
-
-
public void heapify(ArrayList<ListNode> heap, int index) {
-
int position = index;
-
int left = 2 * index + 1;
-
int right = 2 * index + 2;
-
-
if(left < heap.size() && heap.get(left).val < heap.get(position).val) {
-
position = left;
-
}
-
-
if(right < heap.size() && heap.get(right).val < heap.get(position).val) {
-
position = right;
-
}
-
-
if (position != index) {
-
ListNode temp = heap.get(position);
-
heap.set(position, heap.get(index));
-
heap.set(index, temp);
-
heapify(heap, position);
-
}
-
}
-
-
public void minHeapify(ArrayList<ListNode> heap) {
-
for (int i = heap.size()/2 - 1; i >= 0; i--) {
-
heapify(heap, i);
-
}
-
}
-
}
阅读(2260) | 评论(0) | 转发(0) |