brezezee

有序矩阵第K小的数

bool check(vector<vector<int>>& matrix, int mid, int k, int n) {
    int i = n - 1;
    int j = 0;
    int num = 0;
    while (i >= 0 && j < n) {
        if (matrix[i][j] <= mid) {
            num += i + 1;
            j++;
        } else {
            i--;
        }
    }
    return num >= k;
}

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    int left = matrix[0][0];
    int right = matrix[n - 1][n - 1];
    // 这里的左右边界用的是数值而不是下标，根据数值确定左上角的数量
    while (left < right) {
        int mid = left + ((right - left) >> 1);  // 这里判断的性质需要O(n)确定数量
        if (check(matrix, mid, k, n)) {         // 这里二分模板用的是满足右半区间性质的，因此得到右边性质里最左端的点
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}