合并K个有序数组

在之前的面试中有遇到这个问题，当时答得不是很满意，所以，下来之后把这个题完整的写了一下。
问题：有K个长度为N的有序数组，将着这些个数组合并为一个有序的数组。
将原问题解决后，我又将原问题修改了一下：
有K个长度不定的有序数组，将这些数组合并为一个有序数组；

三种解法：

1. 申请一个数组，将所有的元素添加到该数组中，使用sort()函数，直接进行排序；
2. 归并排序；两两归并，使用merge()函数；
3. 构造小根堆；

第一种解法的时间复杂度为：O(nlog2n)
第二种解法的时间复杂度为：O(knlogn)
第三种解法的时间复杂度为：O(mnlogn)（m为元素总个数）
第一二种解法，比较简单，这里不再赘述。下面只分析第三种解法；

解法三解题思路：

1. 首先遍历所有的数组，确定最终所有元素的个数(count)；
2. 创建一个大小为count的数组用来保存最终结果，再创建一个大小为K的小根堆；（小根堆保存的元素类型，是结构体）
3. 先将每个数组的第一个元素插入到小根堆中，进行一次堆排序；
4. 重复下面的操作，直至元素全部插入结果集中：
   a. 取出堆顶元素(堆中最小元素),保存到结果中；
   b. 将堆顶元素所在数组的下一个元素替换到堆顶，如果堆顶元素是其所在数组的最后 一个,将堆顶元素替换成INT_MAX;
   c. 进行一次堆排序；

下面是该题的详细解法：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct Node
{
	int val;
	int col;
	int row;
	Node(int _val, int _row, int _col) 
		:val(_val)
		,row(_row)
		,col(_col)
	{}
};

//向下调整
void Adjust(vector<Node*>& heap, int parent)
{
	size_t child = parent * 2 + 1;
	while (child < heap.size())
	{
		if (child + 1 < heap.size() && heap[child + 1]->val < heap[child]->val)
			child++;
		if (heap[child]->val < heap[parent]->val)
			swap(heap[child], heap[parent]);
		parent = child;
		child = parent * 2 + 1;
	}
}
void Heap_Sort(vector<Node*>& heap)
{
	int parent = heap.size() / 2 - 1;
	for (int i = parent; i >= 0; --i)
		Adjust(heap, parent);
}
vector<int> MergeArrays(vector<vector<int>>& arrs)
{
	vector<int> res;
	int count = 0;
	vector<Node*> heap;//这里也可以使用优先级队列或者set，不需要排序的过程；
	for (size_t i = 0; i < arrs.size(); ++i)
	{
		heap.push_back(new Node(arrs[i][0],i,0));
		count += arrs[i].size(); //用来确定最终的循环次数
	}
	//先将堆中元素排序
	Heap_Sort(heap);
	while (count--)
	{
		//将堆顶元素(最小值)插入到结果数组中
		res.push_back(heap[0]->val);
		//判断堆顶元素是不是其数组的最后一个元素
		if (heap[0]->col == arrs[heap[0]->row].size() - 1)
		{
			heap[0]->val = INT_MAX;//将堆顶元素替换成最大值；
			heap[0]->col = INT_MAX;
			heap[0]->row = INT_MAX;
		}
		else
		{
			heap[0]->val = arrs[heap[0]->row][heap[0]->col + 1];
			heap[0]->row = heap[0]->row;
			heap[0]->col = heap[0]->col + 1;
		}
		Adjust2(heap, 0);
	}
	return res;
}
int main()
{
	vector<vector<int>> arrs{ {1,2,7,9}, {5,6}, {3}, {4,8} };
	vector<int> res = MergeArrays(arrs);
	for (auto c : res)
		cout << c << " ";
	cout << endl;
	return 0;
}

这里的小根堆也可以用set来保存，这样就可以直接从set中取出最小元素，而不需要自己来编写排序的过程。