401 · 排序矩阵中的从小到大第k个数

链接：LintCode 炼码 - ChatGPT！更高效的学习体验！

题解： 九章算法 - 帮助更多程序员找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧

class Solution {
public:/*** @param matrix: a matrix of integers* @param k: An integer* @return: the kth smallest number in the matrix*/
class Node {
public:Node(int v, int i):val(v),index(i) {}bool operator < (const Node& node) const {return val > node.val ? true : false;}int val;int index;
};int kthSmallest(vector<vector<int>> &matrix, int k) {// write your code hereint m = matrix.size();if (m <= 0) {return 0;}int n = matrix[0].size();if (n <= 0) {return 0;}std::vector<bool> distance(m*n, false);distance[0] = true;std::priority_queue<Node> que;que.push(Node(matrix[0][0], 0)); int i = 1;std::vector<std::vector<int>> direction{{0, 1}, {1, 0}};while (!que.empty()) {auto f = que.top();que.pop();if (i >= k) {return f.val;}for (int j = 0; j < direction.size(); ++j) {int next_row = f.index / n + direction[j][0];int next_col = f.index % n + direction[j][1];if (next_row < 0 || next_col < 0 || next_row >= m || next_col >= n) {continue;}int node = next_row * n + next_col;if (distance[node]) {continue;}que.push(Node(matrix[next_row][next_col], node));distance[node] = true;}++i;}return -1;}
};