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

难度 中等

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：

matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, 返回 13。

提示： 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix

解法一：直接排序

class Solution { public int kthSmallest(int[][] matrix, int k) { int rows = matrix.length, columns = matrix[0].length; int[] sorted = new int[rows * columns]; int index = 0; for (int[] row : matrix) { for (int num : row) { sorted[index++] = num; } } Arrays.sort(sorted); return sorted[k - 1]; } }

复杂度分析

时间复杂度：O(n² * log_n)，对 n² 个数进行排序空间复杂度：O(n²) ，在 sorted 中存储二维数组中所有数。

解法二：二分法

思路：

取矩阵中最小元素和最大元素的中间值 mid，即 mid = left + ((right - left) >> 1)，然后从二维数组左下边界向右上边界寻找 小于等于 mid 的元素的个数 num，

如果 num < k， 则 left = mid + 1如果 num >= k， 则 left = mid

重复上述操作直到 left >= right

如何统计矩阵中不大于 mid 的元素个数

让其和一列的最下元素进行比较如果大于等于它，就大于等于它上边所有数和它自己，个数累加进去，考察下一列(j++)否则，留在当前列，和上边较小的一个比较(i–) class Solution { public int kthSmallest(int[][] matrix, int k) { int n = matrix.length; int left = matrix[0][0]; int right = matrix[n - 1][n - 1]; while(left < right) { int mid = left + ((right - left) >> 1); if(lessThan_K(matrix, mid, k, n)) { right = mid; }else { left = mid + 1; } } return left; } //从二维数组左下边界向右上边界寻找 小于等于 mid 的元素的个数 private boolean lessThan_K(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); //如果该位置 <= mid ， 则累加上该列包含的元素个数 j++; }else { i--; //换到下一行 } } return num >= k; } }

复杂度分析

时间复杂度：O(nlog_{(right−left)})，二分查找进行次数为 O(log_{(right−left)})，每次操作时间复杂度为 O(n)。空间复杂度：O(1)