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
priority_queue
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
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
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
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;
}
};
发表评论