开发公司网站建设输入搜索内容

23. 合并 K 个升序链表

这题非常容易想到归并排序的思路，俩升序序列合并，可以使用归并的方法。

不过这里显然是一个多路归并排序；包含多个子数组的归并算法，这可以让我们拓展归并算法的思路。

假设n是序列个数，ni是单个序列长度，length是单个序列最大长度

1、顺序单次归并

从左往右依次进行归并，但是这种方法存在一定的缺点。假设n是序列个数，ni是单个序列长度，根据题设，这个方法的最大比较次数至少是：
$n1+(n1+n2)+(n1+n2+n3)\cdot \cdot \cdot =n\ast n1+(n-1)\ast n2+(n-2)\ast n3\cdot \cdot \cdot <=n\ast (n1+n2+n3+\cdot \cdot \cdot )=n^2\ast length<=10^4\ast 500\ast 10^4$
这相当于每个序列都需要被比较序列个数次，这换成是多路归并的数组合并也是一样的。

官方：

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode * head = nullptr;for(int i = lists.size() - 1;i >= 0; --i){head = merge(head, lists[i]);ListNode * temp = head;}return head;}
private:ListNode * merge(ListNode * p,ListNode * q){if(!p) return q;if(!q) return p;ListNode * head = p;if(head->val > q->val) head = q;if(head == p) p = p->next;else q = q->next;ListNode * temp = head;while(p && q){if(p->val > q->val){head->next = q;q = q->next;}else{head->next = p;p = p->next;}head = head->next;}head->next = p ? p : q;return temp;}
};

2、分治归并

使用分治的思想排序是很容易想到的，但是不能很容易的知道分治归并速度一定更快，接下来让我详细思考一下是否会更快：
我们可以考虑，每次将序列数量减半合并，那么每一层合并使用的时间是$O(length\ast n)$，我们知道每层数量减半，那么一共是有$O(logn)$层，所以时间复杂度为$O(nlogn\ast length)$

为什么分治归并会比普通顺次归并要快？
可以这样看一下，使用分治，将所有数分为两个区间[l,mid]和[mid+1,r]，左区间的数 和 右区间的数只会在最后合并时比较一次，其他时候打死不相往来。而使用顺序归并，左区间的数 和 右区间的数会比较很多次，在考虑到

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.size() == 0) return nullptr;return mergesort(lists, 0, lists.size() - 1);}
private:ListNode * merge(ListNode * p,ListNode * q){if(!p) return q;if(!q) return p;ListNode * head = p;if(head->val > q->val) head = q;if(head == p) p = p->next;else q = q->next;ListNode * temp = head;while(p && q){if(p->val > q->val){head->next = q;q = q->next;}else{head->next = p;p = p->next;}head = head->next;}head->next = p ? p : q;return temp;}ListNode * mergesort(vector<ListNode*>& lists,int left,int right){if(left == right) return lists[left];int mid = (left + right) >> 1;ListNode * p = mergesort(lists,left,mid);ListNode * q = mergesort(lists,mid + 1, right);return merge(p, q);}
};

3、使用优先队列合并

这种方式非常牛。

我们将所有序列，依据序列头部的元素大小放入一个优先队列，那么这个优先队列的深度是$logn$，然而我们每次取出一个结点它的头部必然是现在里面最小的，将它放入待合并的目标序列中，然后将该序列后移一位，插入到优先队列中。因此每个元素插入时间是$O(logn)$，一共有$(length\ast n)$个元素。所以总时间为$O(nlogn\ast length)$

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.size() == 0) return nullptr;priority_queue<ListNode *,vector<ListNode *>,Sort> q;for(int i = lists.size() - 1;i >= 0; --i) if(lists[i]) q.push(lists[i]);ListNode * dummy = new ListNode;ListNode * temp = dummy;while(!q.empty()){ListNode * head = q.top();q.pop();temp->next = head;temp = temp->next;head = head->next;if(head) q.push(head);}temp = dummy->next;delete dummy;return temp;}
private:struct Sort{bool operator ()(const ListNode * a,const ListNode * b){return a->val > b->val;}};
};

能够实现优先队列，那么这个问题就很容易被解决。

• 我们需要注意两个问题
  • 优先队列使用的比较函数必须自定义为结构体或者符号重载
  • 优先队列使用的比较函数的大于号小于号取值，和sort刚好相反。

使用方式：

priority_queue<Exp,vector<Exp>,cmp> q;

struct cmp{bool operator() (Exp a, Exp b){if() return true;return false;}
}

唯一变化的就是括号里面的类型Exp和你想要定义的比较方式。