mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
82 lines
3.8 KiB
Markdown
82 lines
3.8 KiB
Markdown
# [378. Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/)
|
||
|
||
# 思路
|
||
这道题让我们求各行各列分别有序的矩阵中第K小的元素。难点在于矩阵只是局部（各行或各列）有序，整体可能是无序的。
|
||
|
||
由于是有序的，所以很容易想到可以用二分查找解此题。由于一般的二分都是对数组的下标二分，所以很容易陷入这个定势思维中去。
|
||
|
||
这里我们需要对元素二分而不是元素的下标二分:
|
||
我们很容易知道整个矩阵的最大值high和最小值low分别是右下角和左上角元素，所以最终的结果就是在区间[low, high]内。
|
||
设`mid = (low+high)/2`，那么该如何更新low和high呢？我们可以计算有多少个（设为count）数小于等于mid，那么
|
||
* 若`count < k`，说明不到k个数小于等于mid，即最终结果肯定大于mid，所以更新`low = mid + 1`；
|
||
* 否则，说明至少k个数小于等于mid，即最终结果肯定不大于mid，所以更新`high = mid`（**注意这里没有减一**）。
|
||
|
||
所以问题的关键就在于如何计算有多少个数小于等于mid，分为两个思路。
|
||
|
||
## 思路一
|
||
|
||
我们一行一行（或者一列一列）地遍历矩阵，计算每一行有多少个数小于mid，最后累加起来就可以了。
|
||
对于每一行，因为是有序的，所以我们可以用二分查找的思路计算有多少个数小于mid，可直接使用STL中的`upper_bound`函数：
|
||
* `upper_bound(first, last, val)`返回有序数组或容器的`[first, last)`范围内第一个大于val的元素的位置(指针或者迭代器);
|
||
> 而`lower_bound(first, last, val)`返回有序数组或容器的`[first, last)`范围内第一个大于或等于val的元素的位置;
|
||
|
||
总的时间复杂度即O(nlogn * logM)，其中M等于最大值与最小值的差值。
|
||
|
||
## 思路二
|
||
|
||
思路一只利用了行有序（或只利用了列有序），所以还有优化的空间。
|
||
|
||
我们从左下角出发（或者从右上角出发，类似），
|
||
* 若当前值（设下标为i,j）小于等于mid，因为当前值正上方的值更小些，所以累加上这些值的个数`count += (i+1)`，然后往右移（j++）进入下一循环；
|
||
* 否则，即当前值大于mid，那我们只需上移（i--）即可。
|
||
|
||
由于我们只会右移或者上移，所以移动步数为2n，即线性复杂度。所以总的时间复杂度为O(n * logM)，其中M等于最大值与最小值的差值。
|
||
|
||
# C++
|
||
## 思路一
|
||
``` C++
|
||
class Solution {
|
||
private:
|
||
// 记录有多少数小于等于target
|
||
int Count_No_Greater(const vector<vector<int>>& matrix, int target){
|
||
int n = matrix.size(), count = 0;
|
||
for(int i = 0; i < n; i++)
|
||
count += upper_bound(matrix[i].begin(),
|
||
matrix[i].end(), target) - matrix[i].begin();
|
||
return count;
|
||
}
|
||
public:
|
||
int kthSmallest(vector<vector<int>>& matrix, int k) {
|
||
int n = matrix.size();
|
||
int low = matrix[0][0], high = matrix.back().back();
|
||
|
||
while(low < high){
|
||
int mid = (high - low) / 2 + low;
|
||
// count记录有多少数小于等于mid
|
||
int count = Count_No_Greater(matrix, mid);
|
||
if(count < k) low = mid + 1; // 不到k个数小于等于mid
|
||
else high = mid; // 至少k个数小于等于mid
|
||
}
|
||
return low;
|
||
}
|
||
};
|
||
```
|
||
|
||
## 思路二
|
||
仅`Count_No_Greater`函数与思路一不同
|
||
``` C++
|
||
// 记录有多少数小于等于target
|
||
int Count_No_Greater(const vector<vector<int>>& matrix, int target){
|
||
int n = matrix.size(), count = 0;
|
||
int i = n - 1, j = 0;
|
||
while(i >= 0 && j < n){
|
||
if(matrix[i][j] > target) i--;
|
||
else{
|
||
count += (i + 1);
|
||
j++;
|
||
}
|
||
}
|
||
return count;
|
||
}
|
||
```
|