本文共 1831 字，大约阅读时间需要 6 分钟。
为了解决这个问题，我们需要找到一个 n x n 矩阵中第 k 小的元素。矩阵的每一行和每一列都是已排序的。我们可以利用二分查找的方法来高效地解决这个问题。
问题分析：由于矩阵的每一行和每一列都是有序的，我们可以利用二分查找来减少搜索范围。目标是找到第 k 小的元素，这可以通过二分查找来实现。
二分查找：我们将矩阵的最小元素作为左边界，最大元素作为右边界。然后，我们不断缩小查找范围，直到找到正确的元素。每次我们计算中间值 mid，并计算在矩阵中比 mid 小的元素个数。如果这个个数小于 k，说明 mid 太小，需要在左边界往右调整；否则，右边界往左调整。
辅助函数：我们需要一个辅助函数 countSmall 来计算在某一列中比给定值小的元素个数。由于每一列是有序的，我们可以使用二分查找来高效地计算该数目。
class Solution { public int kthSmallest(int[][] matrix, int k) { int left = matrix[0][0]; int right = matrix[matrix.length - 1][matrix[0].length - 1]; while (left < right) { int mid = left + (right - left) / 2; int count = 0; for (int i = 0; i < matrix.length; i++) { count += countSmall(matrix, mid, i); } if (count < k) { left = mid + 1; } else { right = mid; } } return left; } public int countSmall(int[][] matrix, int num, int i) { if (num < matrix[i][0]) { return 0; } if (num >= matrix[i][matrix[i].length - 1]) { return matrix[i].length; } int left = 0; int right = matrix[i].length - 1; while (left < right) { int mid = left + (right - left) / 2; if (matrix[i][mid] > num && matrix[i][mid - 1] <= num) { return mid; } if (matrix[i][mid] > num) { right = mid; } else { left = mid + 1; } } return left + 1; }} kthSmallest 函数：这个函数负责进行二分查找。初始时，左边界是矩阵的最小元素，右边界是矩阵的最大元素。然后，我们不断调整查找范围，直到找到正确的元素。
countSmall 函数：这个函数用于计算在某一列中比给定值小的元素个数。由于每一列是有序的，我们可以使用二分查找来高效地找到结果。
二分查找过程：每次计算中间值 mid，然后通过 countSmall 函数计算比 mid 小的元素个数。如果这个个数小于 k，说明 mid 太小，调整左边界；否则，调整右边界。
这种方法通过二分查找和辅助函数，能够在较短的时间内高效地找到第 k 小的元素。
转载地址：http://xkxx.baihongyu.com/