有序矩阵中第 K 小的元素-Toy模板网

这篇具有很好参考价值的文章主要介绍了有序矩阵中第 K 小的元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接

有序矩阵中第 K 小的元素

题目描述

文章来源地址https://www.toymoban.com/news/detail-808094.html

注意点

每行和每列元素均按升序排序
找到一个内存复杂度优于 O(n²) 的解决方案

解答思路

使用二分查找，思路为：
（1）因为左上角的元素值更小，右下角的元素值更大，先将left设置为左上角元素的值，right设置为右下角元素的值；
（2）判断不大于left和right中间值mid的元素数量sum；
（3）如果sum小于k，则将left设置为mid + 1，否则将right设置为mid。
不断重复上述过程，直到满足sum等于k时right的最小值，此时left等于right，且right是大于等于矩阵中K个元素的临界点，所以矩阵中一定会有一个元素等于right（否则说明并没有找到sum等于k时right的最小值），right也就是有序矩阵中第 K 小的元素

代码

class Solution {
    int n;
    public int kthSmallest(int[][] matrix, int k) {
        n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + (right - left) / 2;
            int sum = countLessThanMid(matrix, mid);
            if (sum < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public int countLessThanMid(int[][] matrix, int mid) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            // 如果左上角都大于mid，则一定没有小于等于mid的元素存在
            if (matrix[i][0] > mid) {
                return sum;
            }
            // 如果右上角都小于等于mid，则该行所有元素都小于等于mid
            if (matrix[i][n - 1] <= mid) {
                sum += n;
                continue;
            }
            // 其余情况查找改行小于等于mid的元素
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] > mid) {
                    break;
                }
                sum++;
            }
        }
        return sum;
    }
}

关键点

二分查找的思路
怎么找到sum等于k时right的最小值
当right - left=1，且两个数都是负数的时候，求mid时会等于right的值，此时如果sum >= k，则会一直卡在循环中无法跳出，需要保证这种特殊情况求mid也是left，所以求mid时使用left + (right - left) / 2

到了这里，关于有序矩阵中第 K 小的元素的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！