image.png

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
//創(chuàng)建一個(gè)空最小堆
        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();//逐個(gè)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;
    }
};