378. 有序矩阵中第K小的元素

这道题也是求第$k$小的元素，只不过是整数，由于这是一个未排好的序列，所以用索引二分法不可行，只能按值来二分。由题中矩阵的性质来看，整个序列的范围是$[matrix[0][0],matrix[n-1][n-1]]$，是左闭右闭的，我们初始化$l=matrix[0][0]$，$r=matrix[n-1][n-1]$。

按值二分，那么我们每次的$mid$都是一个猜测出来的数，我们要求的就是序列中小于等于$mid$的数量，那么如果此数量< $k$，我们令$l=mid+1$，如果此数量 >= $k$，我们令$r=mid$。当$l == r$时，我们结束循环，返回$l 或 r$。

疑问1：解释一下每次$l$和$r$取值的原因

当数量小于$k$时，那么此时的$mid$是不符合题意的，应当被剔除，所以$l = mid+1$后范围变成了[mid+1,r]，这是毫无疑问的；

当数量大于等于$k$，我们此时做了统一的处理就是$r = mid$，发现无论是大于还是等于，这个$mid$都做出了保留，这是因为我们求的是小于等于$mid$的数量，而且序列中有取值相同的元素，这些元素虽然位置不同，但是求出的数量是相同的，所以当数量大于$k$时，这个$mid$有可能是目标解，所以我们不能去除掉，所以得到$[l,mid]$。

疑问2：最终返回的是$l$(或$r$)，一定能保证返回的值在序列中？

答案是一定的，虽然$l、r、mid$都是猜测值，但是我们发现代码是在循环结束后返回了唯一值，而在循环内没有返回值，这是因为：

• 可能找不到数量等于$k$的$mid$(因为有值相同的元素)
• 虽然找到了数量等于$k$的$mid$，但是毕竟$mid$是猜测值，我们没有办法保证$mid$一定在序列中

所以我们在循环中是没办法返回答案的。

虽然我们没法确保$mid$是序列中的值，而且可能找不到数量等于$k$的$mid$，但是我们在循环中每一步都保证目标解都在范围内，所以我们等到$l == r$时，此时范围内只有一个解了，这个解一定就是目标解了。

代码

至于如何求数量，可以去看官方题解。

class Solution {
public:
    int getSum(const vector<vector<int>> &matrix , int k , int mid){
        int n = matrix.size();
        int i = n-1 , j = 0;
        int res = 0;
        while(i >=0 && j < n){
            if(matrix[i][j] <= mid){
                res += i+1;
                ++j;
            }
            else --i;
        }
        return res;
    }
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int l = matrix[0][0] , r = matrix[n-1][n-1];
        while(l < r){
            int mid = (l + r) / 2;
            int sum = getSum(matrix , k , mid);
            if(sum >= k){
                r = mid;
            }
            else l = mid + 1;
        }
        return r;
    }
};