image.png
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
//创建一个空最小堆
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> q;
for(int i=0;i<matrix.size();i++){
q.push(make_pair(matrix[i][0],make_pair(i,0)));
}
while(k-1){
pair<int,pair<int,int>> temp = q.top();
q.pop();//逐个pop，pop到第k-1 然后最小堆，堆顶就是result
if(temp.second.second != matrix.size()-1){
q.push(make_pair(matrix[temp.second.first][temp.second.second+1],make_pair(temp.second.first,temp.second.second+1)));
}
k--;
}
return q.top().first;
}
};
