leetcode - [378] Kth Smallest Element in a Sorted Matrix

2020/08/28

问题描述

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

给你一个n * n的矩阵,请找出第k小的元素,该矩阵符合以下性质:

  • 每行均递增

举个例子:

解法1

Thanks @Sheep

梳理下思路:

首先,我们需要使用二分思想,不断计算矩阵中小于等于x的元素个数。

那么,当前x如何获得?

我们可以从矩阵中发现一个规律,最小值在左上角,也就是l = matrix[0][0]

最大值在右下角,也就是r = matrix[n - 1][n - 1]

所以,x每次取l + r >>> 1即可。

接着,如何快速计算矩阵中小于等于x的元素个数?

我们先规定一个起点,也就是第一行的最右侧j = n - 1; start = matrix[0][j]

如果x >= start,那么cnt += j + 1; i++,否则j--,举个例子:

来看下实现:

class Solution {

    private int numbersLessThanOrEqual(int[][] matrix, int n, int mid){
        int cnt = 0;
        int i = 0, j = n - 1;
        while (i < n && j >= 0){
            if (matrix[i][j] <= mid){
                cnt += j + 1;
                i++;
            } else {
                j--;
            }
        }
        return cnt;
    }

    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        if (n == 0 || matrix[0].length == 0) return -1;
        int l = matrix[0][0], r = matrix[n - 1][n - 1];
        while (l < r){
            int mid = l + r >>> 1;
            if (numbersLessThanOrEqual(matrix, n, mid) >= k) r = mid;
            else l = mid + 1;
        }
        return r;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory