小辰青岛网站建设,信息可视化网站,合肥做企业网站,大气公司网站源码链接#xff1a;LintCode 炼码 - ChatGPT#xff01;更高效的学习体验#xff01;
题解#xff1a; 九章算法 - 帮助更多程序员找到好工作#xff0c;硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧
class Solution {
public:/*** param matrix: a matrix of intege…
链接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(vectorvectorint 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::vectorbool distance(m*n, false);distance[0] true;std::priority_queueNode que;que.push(Node(matrix[0][0], 0)); int i 1;std::vectorstd::vectorint 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;}
};
