题目
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
思路
这里是一个很常规的问题，合并k个有序的数组。首先看看合并两个有序的数组会怎么做，这个问题是不是很熟悉。一下就想到了归并排序的合并步骤，在两个数组中设计两个index，即index1，index2。
a[index1] < b[index2] => c[index1 + index2 - 1] = a[index1], index1 ++
a[index1] >= b[index2] => c[index1 + index2 - 1] = b[index2], index2 ++
如果数组a的长度为n，数组b的长度为m，即O(n+m)的复杂度可以解决这个问题，那么现在2个数组变成了k个数组，我们是不是可以使用同样的方法呢？
肯定是可以的，不过我们现在是需要在k个索引数中找到最小的一个，并且把它赋值给最终的结果数组，并把索引增加。那这个子问题其实也是很熟悉的一个子问题，动态维护最小值，因为是全段最小，所以我们选用堆来维护。如果是维护区间最小，我们也可以用线段树来实现。
那么我们只需要在一开始的时候建立一个大小为k的堆（即将每个数组的第一个数加入堆，并从下向上维护一次堆），这里建堆的复杂度为O(klogk)。然后每次将堆头加入最终的答案数组，并将其换成它的下一个，并从上向下维护一次堆，这里的单此维护代价是O(logk)，总维护代价是O(nlogk)。
代码
这里是使用链表实现的，总体思路不变，比较烦的是判断空链表的情况。
/**
* 交换两个节点
*
* @param lists
* @param a
* @param b
*/
public void changeNode(ListNode[] lists, int a, int b) {
ListNode c = lists[a];
lists[a] = lists[b];
lists[b] = c;
}
/**
* 向上调整堆
*
* @param heap
* @param root
*/
public void makeHeap(ListNode[] heap, int root) {
if (root == 0) return;
int fa = (root + 1) / 2 - 1;
int change = root % 2 == 0 ? (heap[root - 1].val < heap[root].val ? root - 1 : root) : root;
if (heap[fa].val > heap[change].val) {
changeNode(heap, fa, change);
makeHeap(heap, fa);
}
}
/**
* 向下调整堆
*
* @param heap
* @param l
*/
public void adjustHeapDown(ListNode[] heap, int l) {
int lc = 0, rc = 0, change = 0;
while (l * 2 + 1 < heap.length) {
lc = l * 2 + 1;
rc = l * 2 + 2;
change = rc >= heap.length ? lc : (heap[lc].val < heap[rc].val ? lc : rc);
if (heap[change].val < heap[l].val)
changeNode(heap, l, change);
else
break;
l = change;
}
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0 || lists == null) return null;
int len = 0;
for (int i = 0; i < lists.length; i++) {
len += lists[i] != null ? 1 : 0;
}
if (len == 0) return null;
ListNode[] heap = new ListNode[len];
len = 0;
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
heap[len] = lists[i];
makeHeap(heap, len);
len++;
}
}
ListNode ans = heap[0];
ListNode res = ans;
while (true) {
heap[0] = heap[0].next != null ? heap[0].next : new ListNode(Integer.MAX_VALUE);
adjustHeapDown(heap, 0);
if (heap[0].val == Integer.MAX_VALUE) break;
res.next = heap[0];
res = heap[0];
}
return ans;
}
PriorityQueue
因为最近在学习Java，对应该功能的实现，Java中有一种数据结构PriorityQueue。其实底层的实现就是最小堆，相信最小堆的实现大家都很熟悉，这边就不赘述，这里仅仅记录一下API。
- 向优先队列添加元素[O(logn)]：
- add(E e)：插入失败时，抛出异常
- offer(E e)：插入失败时，返回false
- 获取但不删除队首元素[O(1)]：
- element()：获取失败时，抛出异常
- peek()：获取失败时，返回null
- 获取并且删除队首元素[O(logn)]：
- remove()：获取失败时，抛出异常
- poll()：获取失败时，返回null
- 删除元素[O(logn)]：
- remove(Object o)：删除优先队列中等于o的元素
PriorityQueue的具体分析见：深入理解Java PriorityQueue
