在一个排序矩阵中找从小到大的第 k 个整数。
排序矩阵的定义为：每一行递增，每一列也递增。
样例
给出 k = 4 和一个排序矩阵：
[
[1 ,5 ,7],
[3 ,7 ,8],
[4 ,8 ,9],
]
返回 5。
挑战:使用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;
}
}
}
};
