LeetCode 378 Kth Smallest Element in a Sorted Matrix
概述
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
空间复杂度要求优于 O(n^2)。
暴力法
将各个有序的列合并到一整个列,空间复杂度 O(n),用来记录每一列搞到哪里了。
时间复杂度 O(kn)。
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int c = 0;
vector<int> indices(matrix.size(), 0);
int minr;
while (c < k) {
int minv = INT_MAX;
for (int r = 0; r < matrix.size(); r ++) {
if (indices[r] < matrix.size() && matrix[r][indices[r]] < minv) {
minv = matrix[r][indices[r]];
minr = r;
}
}
indices[minr] ++;
c ++;
}
return matrix[minr][indices[minr] - 1];
}
};
二分搜索法
我们要找的无非就是一个值,该值存在于矩阵中,且小于该值的数值个数为 k,那我们自然可以二分搜索该数。
二分搜索复杂度为 O(log(n^2)),每次要统计小于该值的数值个数,用二分搜索来搜索每行来进行寻找,复杂度 O(nlogn), 因此总的时间复杂度为 O(2n(logn)^2)
class Solution
{
public:
int kthSmallest(vector<vector<int>>& matrix, int k)
{
int n = matrix.size();
int le = matrix[0][0], ri = matrix[n - 1][n - 1];
int mid = 0;
while (le < ri)
{
mid = le + (ri-le)/2;
int num = 0;
for (int i = 0; i < n; i++)
{
int pos = upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
num += pos;
}
if (num < k)
{
le = mid + 1;
}
else
{
ri = mid;
}
}
return le;
}
};