-
Notifications
You must be signed in to change notification settings - Fork 299
/
Code02_KthSmallestElementInSortedMatrix.java
110 lines (96 loc) · 2.33 KB
/
Code02_KthSmallestElementInSortedMatrix.java
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package class17;
import java.util.Comparator;
import java.util.PriorityQueue;
// 本题测试链接 : https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
public class Code02_KthSmallestElementInSortedMatrix {
// 堆的方法
public static int kthSmallest1(int[][] matrix, int k) {
int N = matrix.length;
int M = matrix[0].length;
PriorityQueue<Node> heap = new PriorityQueue<>(new NodeComparator());
boolean[][] set = new boolean[N][M];
heap.add(new Node(matrix[0][0], 0, 0));
set[0][0] = true;
int count = 0;
Node ans = null;
while (!heap.isEmpty()) {
ans = heap.poll();
if (++count == k) {
break;
}
int row = ans.row;
int col = ans.col;
if (row + 1 < N && !set[row + 1][col]) {
heap.add(new Node(matrix[row + 1][col], row + 1, col));
set[row + 1][col] = true;
}
if (col + 1 < M && !set[row][col + 1]) {
heap.add(new Node(matrix[row][col + 1], row, col + 1));
set[row][col + 1] = true;
}
}
return ans.value;
}
public static class Node {
public int value;
public int row;
public int col;
public Node(int v, int r, int c) {
value = v;
row = r;
col = c;
}
}
public static class NodeComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o1.value - o2.value;
}
}
// 二分的方法
public static int kthSmallest2(int[][] matrix, int k) {
int N = matrix.length;
int M = matrix[0].length;
int left = matrix[0][0];
int right = matrix[N - 1][M - 1];
int ans = 0;
while (left <= right) {
int mid = left + ((right - left) >> 1);
// <=mid 有几个 <= mid 在矩阵中真实出现的数,谁最接近mid
Info info = noMoreNum(matrix, mid);
if (info.num < k) {
left = mid + 1;
} else {
ans = info.near;
right = mid - 1;
}
}
return ans;
}
public static class Info {
public int near;
public int num;
public Info(int n1, int n2) {
near = n1;
num = n2;
}
}
public static Info noMoreNum(int[][] matrix, int value) {
int near = Integer.MIN_VALUE;
int num = 0;
int N = matrix.length;
int M = matrix[0].length;
int row = 0;
int col = M - 1;
while (row < N && col >= 0) {
if (matrix[row][col] <= value) {
near = Math.max(near, matrix[row][col]);
num += col + 1;
row++;
} else {
col--;
}
}
return new Info(near, num);
}
}