在一個排序矩陣中找從小到大的第 k 個整數(shù)。
排序矩陣的定義為：每一行遞增，每一列也遞增。
樣例
給出 k = 4 和一個排序矩陣：
[
[1 ,5 ,7],
[3 ,7 ,8],
[4 ,8 ,9],
]
返回 5。
挑戰(zhàn):使用O(k log n)的方法，n為矩陣的寬度和高度中的最大值。

注意make_pair() 使用括號

class Solution {
public:
    /**
     * @param matrix: a matrix of integers
     * @param k: an integer
     * @return: the kth smallest number in the matrix
     */
    int kthSmallest(vector<vector<int> > &matrix, int k) {
        // write your code here
        
        int n = matrix.size();
        if(n == 0 || k == 0){
            return 0;
        }
        
        int m = matrix[0].size();
        
        priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > pq;
        map<<pair<int, int>, bool > > visited;
        
        pq.push(make_pair(matrix[0][0], make_pair(0, 0) ));
        visited[make_pair(0, 0)] = true;
        
        while(k--){
            pair<int, pair<int, int> > current = pq.top();
            pq.pop();
            if(k == 0)
                return current.first;
            int nx = current.second.first+1;
            int ny = current.second.second;
            if(nx < n && visited[make_pair(nx, ny)] == false){
                pq.push(make_pair(matrix[nx][ny], make_pair(nx, ny)));
                visited[make_pair(nx, ny)] = true;
            }
            
            nx = current.second.first;
            ny = current.second.second+1;
            if(ny < m && visited[make_pair(nx, ny)] == false){
                pq.push(make_pair(matrix[nx][ny], make_pair(nx, ny)));
                visited[make_pair(nx, ny)] = true;
            }
        }
    }
};