一般来说 ，可能k有序数组的元素个数不一定。(假设有序数组从小到大) 思路如下 ， 建立大小为k的小根堆，刚开始取k个数组的头结点放入堆中。**后面我们用堆顶元素来源的数组的下一个元素进行替换。**每次将堆顶元素存入结vector ret中。 注意： 1。显然我们需要确定堆顶元素来自于哪个数组，设置标志即可 2。当某一个数组元素为空时（已经取完了）。就不用向堆中替换了
代码如下
#include<iostream> #include<vector> #include<algorithm> #include<queue> using namespace std; typedef struct Node { int val; int col; int row; Node(int _val, int _row, int _col) :val(_val) , row(_row) , col(_col) {} }newNode; struct compare { bool operator()(Node node1, Node node2) { return node1.val > node2.val;//这是小根堆 } }; vector<int> MergeArrays(vector<vector<int>>& arrs) { vector<int> res; priority_queue<Node, vector<Node>, compare> pq; for (size_t i = 0; i < arrs.size(); ++i) { Node node(arrs[i][0], i, 0); pq.emplace(node);//涉及到了移动语义，局部变量也要好好利用。 } while (!pq.empty())//堆里面还有数据 { //将堆顶元素(最小值)插入到结果数组中 Node temp_node = pq.top(); res.push_back(temp_node.val); pq.pop(); //开始像堆中添加元素。判断堆顶元素是不是其数组的最后一个元素 if (temp_node.col == arrs[temp_node.row].size() - 1) { //已经是某一行中的最后一列了。不用添加进去了 continue; } else { Node node(arrs[temp_node.row][temp_node.col+1], temp_node.row, temp_node.col + 1);//将同行的下一个元素放入列中 pq.emplace(node);//涉及到了移动语义，局部变量也要好好利用 } } return res; } int main() { vector<vector<int>> arrs{ {1,2,7,9}, {5,6}, {3}, {4,8} }; //vector<vector<int>> arrs{ {1,2,}, {4} }; vector<int> res = MergeArrays(arrs); for (auto c : res) cout << c << " "; cout << endl; return 0; }里面我为什么使用emplace 而不用push_back 这是为了避免不必要的内存拷贝。这里涉及了移动语义（面试被问过）的知识，大家有兴趣可以看看c++11的新特性。
