378. Kth Smallest Element in a Sorted Matrix

Given a 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 ≤ n2.

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int lb = matrix[0][0], ub = matrix[n - 1][n - 1];

        while(lb < ub){
            int mid = (lb + ub)>>1;
            int num = 0;
            for(int i = 0; i < n; i++){
                //这里保证了ub永远取不到，count取到的是 >mid的第一个数 
                int count = upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
                num += count;
            }

            //在这里需要注意的是有可能求出来的mid值刚好满足条件，这时候mid不在矩阵内(mid不是矩阵内的一个值)
            if(num < k){
                lb = mid + 1;
            }else{
                ub = mid;
            }
        }
        return lb;
    }
};

if(num < k){
                lb = mid + 1;
            }else{
                ub = mid;
            }

分析一下上面为什么这样写？
upper_bound求出的是小于等于mid的元素的个数(upper_bound求出的是大于mid的第一个元素的位置)
lower_bound求出的是小于mid的元素的个数

如果使用lower_bound,那么num就是<mid的元素的个数
(1)num < k 说明小于mid的元素的个数为num个，那么小于等于mid的元素就有可能为k个

(2)num > k说明小于mid的元素的个数大于k个，说明最终的结果一定小于mid(将ub = mid - 1)；

(3)num == k 说明小于mid的元素就有k个，说明最终的结果一定小于mid(将ub = mid - 1)；


综上，会写出如下代码
    lower_bound();
if(num < k){
                lb = mid ;     ....1
            }else{
                ub = mid - 1;  .....2
            }

这个代码有可能会跳不出循环，设想最终的结果是一个区间只有两个数，n那么mid就是左边那部分，执行1后有可能跳不出循环


现在用upper_bound

(1)num < k，说明小于等于mid的元素的个数小于k个，那么如果取mid，那么mid就是第num( < k)小元素，则lb = mid +1;
(2)num > k，说明小于等于mid的元素的个数大于k个，如果mid在矩阵中，那么有可能取到mid(因为mid可能重复),mid不在矩阵中
(3)num == k