Leetcode 378. Kth Smallest Element in a Sorted Matrix

题目链接

Given n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n^2.

思路1

二分枚举答案，用upper_bound去验证这个枚举的数字到底第几小（因为会有重复的数字所以用upper_bound），属于一个优雅的暴力算法。时间复杂度，枚举复杂度，验证复杂度，其中为数字的规模。

代码

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n=matrix.size();
        int l=matrix[0][0],r=matrix[n-1][n-1];
        int mid;
        while(l<r){
            mid = l + (r-l)/2;
            
            // judge
            int rank = 0;
            for(int i=0;i<n;i++){
                // 小小的优化
                if(matrix[i][0]>mid){
                    break;
                }
                rank = rank + (upper_bound(matrix[i].begin(),matrix[i].end(),mid)-matrix[i].begin());
            }
            
            if(rank<k){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return l;
    }
};

小小的优化：因为纵列也有序，所以如果某行的第一个数字就大于当前枚举的答案，就无需判断下面的行。

思路2

基于思路1的二分枚举答案，设这个枚举出的答案为，去检查这个枚举出的答案到底在矩阵里是第几小这边可以借用Leetcode 240的思想，时间复杂度降为，其中为数字规模。

//只改了上面代码judge那一段
int rank=0;
int x=0;
int y=n-1;
while(x<n && y>=0){
    if(matrix[x][y]>mid){
        y--;
    }else{
        x++;
        rank = rank + y + 1;
    }
}