378. Kth Smallest Element in a Sorted Matrix-白红宇

378. Kth Smallest Element in a Sorted Matrix

阅读量：250 次

发布时间：2019-03-01

本文共 1871 字，大约阅读时间需要 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/

你可能感兴趣的文章