Find the kth smallest number in at row and column sorted matrix.
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 = 0; i < matrix.size(); ++i) { for (int j = 0; 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[0][0], right = matrix.back().back(); while (left < right) { int mid = left + (right - left) / 2, cnt = 0; for (int i = 0; i < matrix.size(); ++i) { cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin(); } if (cnt < k) left = mid + 1; 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[0][0], right = matrix.back().back(); while (left < right) { int mid = left + (right - left) / 2; int cnt = search_less_equal(matrix, mid); if (cnt < k) left = mid + 1; else right = mid; } return left; } int search_less_equal(vector<vector<int>>& matrix, int target) { int m = matrix.size(), n = matrix[0].size(), i = m - 1, j = 0, res = 0; while (i >= 0 && j < n) { if (matrix[i][j] <= target) { res += i + 1; ++j; } else { --i; } } return res; } };
本文转自博客园Grandyang的博客，原文链接：有序矩阵中第K小的数字[LintCode] Kth Smallest Number in Sorted Matrix ，如需转载请自行联系原博主。