05 August 2008
给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。
就是先确定左右边界，即最小和与最大和，然后二分得到mid，每次判断和小于mid的数组有多少个，如果大于等于k那么更新r，否则更新l。
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
class Solution {
private int count;
public int kthSmallest(int[][] mat, int k) {
int n = mat[0].length;
int m = mat.length;
int lo = 0;
int hi = 0;
for (int i = 0; i < m; i++) {
lo += mat[i][0];
hi += mat[i][n - 1];
}
int init = lo;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
count = 1;
dfs(mid, 0, init, k, mat);
if (count < k) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
private void dfs(int mid, int index, int sum, int k, int[][] mat) {
int m = mat.length;
int n = mat[0].length;
if (sum > mid || index == m || count > k) {
return;
}
dfs(mid, index + 1, sum, k, mat);
for (int i = 1; i < n; i++) {
if (sum + mat[index][i] - mat[index][0] <= mid) {
count++;
dfs(mid, index + 1, sum + mat[index][i] - mat[index][0], k, mat);
} else {
break;
}
}
}
}