-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathL378.java
More file actions
67 lines (57 loc) · 1.8 KB
/
L378.java
File metadata and controls
67 lines (57 loc) · 1.8 KB
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package com.liang.leetcode.binarySearch;
/**
* @ClassName: L378
* @Description: 有序矩阵中第 K 小的元素
* @Author: LiaNg
* @Date: 2020/3/24 18:21
*/
public class L378 {
public static void main(String[] args) {
L378 l378 = new L378();
int[][] matrix = new int[][]{
{1, 5, 9},
{10, 11, 13},
{12, 13, 15}
};
int k = 8;
System.out.println("l378.kthSmallest(matrix,k) = " + l378.kthSmallest(matrix, k));
}
/**
* 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
* 请注意，它是排序后的第 k 小元素，而不是第 k 个元素。
* 说明:
* 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public int kthSmallest(int[][] matrix, int k) {
int count = 0;
int length = matrix.length;
int l = matrix[0][0];
int r = matrix[length - 1][length - 1];
int m;
while (l <= r) {
m = l + (r - l) / 2;
count = checkCount(matrix, m);
if (count < k) {
l = m + 1;
} else {
r = m - 1;
}
}
return l;
}
public int checkCount(int[][] matrix, int k) {
int n = matrix.length, i = n - 1, j = 0, res = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] <= k) {
res += i + 1;
++j;
} else {
--i;
}
}
return res;
}
}