378. 有序矩阵中第K小的元素。 ①二分

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。

请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：

matrix = [

[ 1, 5, 9],

[10, 11, 13],

[12, 13, 15]

],

k = 8,

返回 13。

1.二分

利用矩阵性质，从右上角开始划分，左上部分的数值总是较小的，利用二分法，划分到左上那堆数字的数量=k、

class Solution {public: 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){语言方法

70952N5im

2aPrj抖音小店怎么开通「详细教程」一看就会

87672007-06-20 23:11:10

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