[LeetCode] 378. Kth Smallest Element in a Sorted Matrix

这道题感觉比较经典，值得收藏一下（感觉是面试喜欢的类型_(:з)∠)_
Kth Smallest Element in a Sorted Matrix

题目描述

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个元素。

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

返回 13。

思路

二分查找，二分的是小于某个值的元素的个数，二分的target仍是当前的左右边界的中间值，根据数组有序，记录小于等于target的元素个数。当这个个数正好是k的时候，左右边界相等。
在计算cnt的时候，利用数组行列有序的性质，从左上角往右上搜，如果当前元素值大于mid，就加上这一行的元素个数（0到当前的行坐标），并把纵坐标向右一个。否则，行坐标减一。

代码

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int left=matrix[0][0];
        int right=matrix.back().back();
        while(left<right)
        {
            int mid=left+(right-left)/2;
            int cnt=count(matrix,mid);
            if(cnt<k)
                left=mid+1;
            else
                right=mid;
        }
        return left;
    }
    int count(vector<vector<int>> &matrix, int mid)
    {
        int res=0;
        int n=matrix.size();
        int i=n-1;
        int j=0;
        while(i>=0&&j<n)
        {
            if(matrix[i][j]>mid)
                i--;
            else
            {
                res+=(i+1);
                j++;
            }
        }
        return res;
    }
};