有序矩阵中第 K 小的元素

发布时间:2024年01月16日

题目链接

有序矩阵中第 K 小的元素

题目描述

注意点

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

解答思路

  • 使用二分查找,思路为:
    (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
文章来源:https://blog.csdn.net/weixin_51628158/article/details/135599622
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。