LeetCode: 378. Kth Smallest Element in a Sorted Matrix

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

378. Kth Smallest Element in a Sorted Matrix

LeetCode - Kth Smallest Element in a Sorted Matrix

这里还是要注意一下：从右上角向左移，从上向下移，可以减少比较次数。

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.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

*Note: * You may assume k is always valid, 1 ≤ k ≤ n².

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Runtime: 0 ms, faster than 100.00% of Java online submissions for Kth Smallest Element in a Sorted Matrix.
 *
 * Memory Usage: 56.2 MB, less than 5.41% of Java online submissions for Kth Smallest Element in a Sorted Matrix.
 *
 * Copy from: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85173/Share-my-thoughts-and-Clean-Java-Code[Share my thoughts and Clean Java Code - LeetCode Discuss]
 */
public int kthSmallest(int[][] matrix, int k) {
    int low = matrix[0][0];
    int length = matrix.length;
    int high = matrix[length - 1][length - 1];
    while (low < high) {
        int mid = low + (high - low) / 2;
        int count = 0;
        int j = length - 1;
        for (int i = 0; i < length; i++) {
            while (j >= 0 && mid < matrix[i][j]) {
                j--;
            }
            count += (j + 1);
        }
        if (count < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}