第378题---Kth Samllest element in a sorted matrix

• 题意描述

  • 给定一个n*n的矩阵，行和列都是递增的，在这个数组找到第k个最小的元素

• 思路：

  • 最大值为a[0][0],最大值为a[n-1][n-1];则元素必定在这两个值之间，然后读两个值的中间值，遍历行判断比这个值小的个数，如果个数<k，则low=mid+1；否则high = mid；

    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            int n = matrix.size();
            int le = matrix[0][0], ri = matrix[n-1][n-1];
            int mid = 0;
            while(le < ri) {
                mid = (le + ri) >> 1;
                int num = 0;
                for(int i = 0; i < n; ++i) {
                    int pos = upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
                    num += pos;
                }
                
                if(num < k) {
                    le = mid + 1;
                } else {
                    ri = mid;
                }
            }
            return le;
        }
    };