友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
378. 有序矩阵中第 K 小的元素
给你一个 n x n 矩阵 matrix，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
你必须找到一个内存复杂度优于 \(O(n^2)\) 的解决方案。
示例 1：
输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 输出：13 解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
示例 2：
输入：matrix = [[-5]], k = 1 输出：-5
提示：
-
n == matrix.length -
n == matrix[i].length -
1 <= n <= 300 -
-109 <= matrix[i][j] <= 109 -
题目数据 保证
matrix中的所有行和列都按 非递减顺序 排列 -
1 <= k <= n2
进阶：
-
你能否用一个恒定的内存(即 \(O(1)\) 内存复杂度)来解决这个问题?
-
你能在 \(O(n)\) 的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了，但是你会发现阅读这篇文章（ this paper ）很有趣。
思路分析
这里还是要注意一下：从右上角向左移，从上向下移，可以减少比较次数。
-
一刷
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;
}