[LintCode] Kth Smallest Number in Sorted Matrix 有序矩阵中第K小的数字
2024-10-21 09:08:12
Find the kth smallest number in at row and column sorted matrix.
Have you met this question in a real interview?
Yes
Example
Given k = 4 and a matrix:
[
[1 ,5 ,7],
[3 ,7 ,8],
[4 ,8 ,9],
]
return 5
Challenge
O(k log n), n is the maximal number in width and height.
LeetCode上的原题，请参见我之前的博客Kth Smallest Element in a Sorted Matrix。
解法一：
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) {
priority_queue<int, vector<int>> q;
for (int i = ; i < matrix.size(); ++i) {
for (int j = ; j < matrix[i].size(); ++j) {
q.push(matrix[i][j]);
if (q.size() > k) {
q.pop();
}
}
}
return q.top();
}
};
解法二：
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) {
int left = matrix[][], right = matrix.back().back();
while (left < right) {
int mid = left + (right - left) / , cnt = ;
for (int i = ; i < matrix.size(); ++i) {
cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
}
if (cnt < k) left = mid + ;
else right = mid;
}
return left;
}
};
解法三：
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) {
int left = matrix[][], right = matrix.back().back();
while (left < right) {
int mid = left + (right - left) / ;
int cnt = search_less_equal(matrix, mid);
if (cnt < k) left = mid + ;
else right = mid;
}
return left;
}
int search_less_equal(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[].size(), i = m - , j = , res = ;
while (i >= && j < n) {
if (matrix[i][j] <= target) {
res += i + ;
++j;
} else {
--i;
}
}
return res;
}
};
最新文章
- WP7系统托盘和应用程序栏
- Github入门（一）
- 【转】Java时间日期包 JodaTime
- cl_gui_cfw=>dispatch
- Leetcode 之Convert Sorted Array to Binary Search Tree（54）
- IIS服务器下301跳转是怎么样实现的？
- Mysql 如何做双机热备和负载均衡
- java面试---summay
- POJ1948Triangular Pastures（DP）
- TRUNCATE TABLE 与 DELETE table 区别
- Eclipse利用代理快速安装插件
- C#List<long>与String（Linq）
- Angular Pipe的应用
- 一起学Android之Storage
- Http和Https有什么区别
- WCF系列_WCF如何选择不同的绑定
- Selenium简单回顾
- 关于pycharm中安装第三方库时报错的解决办法（一）
- switch语句和switch-case与if-else之间的转换
- ubuntu下使用fstab挂载硬盘时，属于root，如何把它改为属于一个用户的（如sgjm)