LeetCode_378 有序矩陣中第K小的元素

題目描述：

給定一個 n x n 矩陣，其中每行和每列元素均按升序排序，找到矩陣中第 k 小的元素。

請注意，它是排序後的第 k 小元素，而不是第 k 個不同的元素。

示例：

matrix = [

[ 1, 5, 9],

[10, 11, 13],

[12, 13, 15]

],

k = 8,

傳回 13。

提示：

你可以假設 k 的值永遠是有效的，1 ≤ k ≤ n2

class Solution {
public:
    //本題類似于合并k個有序連結清單
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        struct Point{
            int val,row,col;
            Point(int val,int row,int col):val(val),row(row),col(col){};
            bool operator > (const Point& a) const{
                return val>a.val;
            }
        };
        priority_queue<Point,vector<Point>,greater<Point>> pq;
        for(int i=0;i<matrix.size();i++){
            //emplace直接構造類對象，并傳入所需要的參數
            pq.emplace(matrix[i][0],i,0);
        }
        for(int i=0;i<k-1;i++){
            Point p=pq.top();
            pq.pop();
            if(p.col!=matrix.size()-1){
                pq.emplace(matrix[p.row][p.col+1],p.row,p.col+1);
            }
        }
        return pq.top().val;
    }
};      

class Solution {
public:
    //本題類似于合并k個有序連結清單
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        struct Point{
            int val,row,col;
            Point(int val,int row,int col):val(val),row(row),col(col){};
        };
        
        struct cmp{
            bool operator()(Point a,Point b){
                return a.val>b.val;
            }
        };
        
        priority_queue<Point,vector<Point>,cmp> pq;
        for(int i=0;i<matrix.size();i++){
            //emplace直接構造類對象，并傳入所需要的參數
            pq.emplace(matrix[i][0],i,0);
        }
        for(int i=0;i<k-1;i++){
            Point p=pq.top();
            pq.pop();
            if(p.col!=matrix.size()-1){
                pq.emplace(matrix[p.row][p.col+1],p.row,p.col+1);
            }
        }
        return pq.top().val;
    }
};