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;
}
};