和合并K个排序链表思路完全相同。 法1：归并 法2：优先级队列（小顶堆）
class Solution { //归并 public: int kthSmallest(vector<vector<int>>& matrix, int k) { vector<int>res = merge(matrix, 0, matrix.size()-1); return res[k - 1]; } vector<int>merge(vector<vector<int>>& matrix, int left, int right)//[left, right]的vector合并排序，成为一个大的有序的vector { if (left == right)return matrix[left]; int mid = left + (right - left) / 2; vector<int>A = merge(matrix, left, mid); vector<int>B = merge(matrix, mid + 1, right); return mergeTwoVector(A, B); } vector<int> mergeTwoVector(vector<int>&A, vector<int>&B)//归并两个升序序列 { vector<int>temp(A.size() + B.size()); int A_start = 0; int B_start = 0; int start = 0; while (A_start < A.size() && B_start < B.size()) { if (A[A_start] <= B[B_start]) { temp[start++] = A[A_start++]; } else { temp[start++] = B[B_start++]; } } if (A_start == A.size()) { while (B_start < B.size()) { temp[start++] = B[B_start++]; } } else { while (A_start < A.size()) { temp[start++] = A[A_start++]; } } return temp; } }; #include <functional> class Solution { //归并 public: int kthSmallest(vector<vector<int>>& matrix, int k) { struct point { int val, x, y; point(int val, int x, int y) : val(val), x(x), y(y) {} bool operator> (const point& a) const { return this->val > a.val; } }; priority_queue<point, vector<point>, greater<point>> pri_queue;//维护一个三个元素的小顶堆 for (int i = 0; i < matrix.size(); i++) { pri_queue.push(point(matrix[i][0], i, 0)); } for (int i = 0; i < k - 1; i++) { point temp = pri_queue.top(); pri_queue.pop(); if (temp.y + 1 < matrix[temp.x].size()) { pri_queue.push(point(matrix[temp.x][temp.y + 1], temp.x, temp.y + 1)); } } return pri_queue.top().val; } };