题目描述
你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
示例 1：
输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释：
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
示例 2：
输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]
提示：
nums.length == k1 <= k <= 35001 <= nums[i].length <= 50-105 <= nums[i][j] <= 105nums[i] 按非递减顺序排列
解法
方法一：排序 + 滑动窗口
思考
要从 \(k\) 个有序列表各取至少一个数，使覆盖区间最短。枚举每个列表的下标组合在总长度较大时不可行。
把所有 \((值, 组号)\) 排成一条有序序列后，问题变成最短窗口恰好覆盖 \(k\) 个组。右端扩张、左端在组数仍为 \(k\) 时收缩，用计数表维护窗口内的组。
我们将每个数字 \(x\) 及其所在的组 \(i\)，构成数据项 \((x, i)\)，存放在一个新的数组 \(t\) 中，然后对 \(t\) 按照数字的大小进行排序（类似于将多个有序数组合并成一个新的有序数组）。
接下来，我们遍历 \(t\) 中的每个数据项，只看其中数字所在的组，用哈希表记录滑动窗口内的数字出现的组，如果组数为 \(k\)，说明当前窗口满足题目要求，此时算出窗口的起始和结束位置，更新答案。
时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为所有数组中数字的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
t = [(x, i) for i, v in enumerate(nums) for x in v]
t.sort()
cnt = Counter()
ans = [-inf, inf]
j = 0
for i, (b, v) in enumerate(t):
cnt[v] += 1
while len(cnt) == len(nums):
a = t[j][0]
x = b - a - (ans[1] - ans[0])
if x < 0 or (x == 0 and a < ans[0]):
ans = [a, b]
w = t[j][1]
cnt[w] -= 1
if cnt[w] == 0:
cnt.pop(w)
j += 1
return ans
|
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 | class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
int n = 0;
for (var v : nums) {
n += v.size();
}
int[][] t = new int[n][2];
int k = nums.size();
for (int i = 0, j = 0; i < k; ++i) {
for (int x : nums.get(i)) {
t[j++] = new int[] {x, i};
}
}
Arrays.sort(t, (a, b) -> a[0] - b[0]);
int j = 0;
Map<Integer, Integer> cnt = new HashMap<>();
int[] ans = new int[] {-1000000, 1000000};
for (int[] e : t) {
int b = e[0];
int v = e[1];
cnt.merge(v, 1, Integer::sum);
while (cnt.size() == k) {
int a = t[j][0];
int w = t[j][1];
int x = b - a - (ans[1] - ans[0]);
if (x < 0 || (x == 0 && a < ans[0])) {
ans[0] = a;
ans[1] = b;
}
if (cnt.merge(w, -1, Integer::sum) == 0) {
cnt.remove(w);
}
++j;
}
}
return ans;
}
}
|
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 | class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int n = 0;
for (auto& v : nums) n += v.size();
vector<pair<int, int>> t(n);
int k = nums.size();
for (int i = 0, j = 0; i < k; ++i) {
for (int v : nums[i]) {
t[j++] = {v, i};
}
}
sort(t.begin(), t.end());
int j = 0;
unordered_map<int, int> cnt;
vector<int> ans = {-1000000, 1000000};
for (int i = 0; i < n; ++i) {
int b = t[i].first;
int v = t[i].second;
++cnt[v];
while (cnt.size() == k) {
int a = t[j].first;
int w = t[j].second;
int x = b - a - (ans[1] - ans[0]);
if (x < 0 || (x == 0 && a < ans[0])) {
ans[0] = a;
ans[1] = b;
}
if (--cnt[w] == 0) {
cnt.erase(w);
}
++j;
}
}
return ans;
}
};
|
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 | func smallestRange(nums [][]int) []int {
t := [][]int{}
for i, x := range nums {
for _, v := range x {
t = append(t, []int{v, i})
}
}
sort.Slice(t, func(i, j int) bool { return t[i][0] < t[j][0] })
ans := []int{-1000000, 1000000}
j := 0
cnt := map[int]int{}
for _, x := range t {
b, v := x[0], x[1]
cnt[v]++
for len(cnt) == len(nums) {
a, w := t[j][0], t[j][1]
x := b - a - (ans[1] - ans[0])
if x < 0 || (x == 0 && a < ans[0]) {
ans[0], ans[1] = a, b
}
cnt[w]--
if cnt[w] == 0 {
delete(cnt, w)
}
j++
}
}
return ans
}
|
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 | impl Solution {
pub fn smallest_range(nums: Vec<Vec<i32>>) -> Vec<i32> {
let mut t = vec![];
for (i, x) in nums.iter().enumerate() {
for &v in x {
t.push((v, i));
}
}
t.sort_unstable();
let (mut ans, n) = (vec![-1000000, 1000000], nums.len());
let mut j = 0;
let mut cnt = std::collections::HashMap::new();
for (b, v) in t.iter() {
let (b, v) = (*b, *v);
if let Some(x) = cnt.get_mut(&v) {
*x += 1;
} else {
cnt.insert(v, 1);
}
while cnt.len() == n {
let (a, w) = t[j];
let x = b - a - (ans[1] - ans[0]);
if x < 0 || (x == 0 && a < ans[0]) {
ans = vec![a, b];
}
if let Some(x) = cnt.get_mut(&w) {
*x -= 1;
}
if cnt[&w] == 0 {
cnt.remove(&w);
}
j += 1;
}
}
ans
}
}
|
方法二：优先队列（小根堆）
思考
方法一先合并再滑窗，要放下全部元素。各列表已有序，可用小根堆始终拿当前 \(k\) 个指针中的最小端，并维护最大值；弹出一组后推进该组指针。空间降到 \(O(k)\)，无需预先展开。
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 | const smallestRange = (nums: number[][]): number[] => {
const pq = new PriorityQueue<number[]>((a, b) => a[0] - b[0]);
const n = nums.length;
let [l, r, max] = [0, Number.POSITIVE_INFINITY, Number.NEGATIVE_INFINITY];
for (let j = 0; j < n; j++) {
const x = nums[j][0];
pq.enqueue([x, j, 0]);
max = Math.max(max, x);
}
while (pq.size() === n) {
const [min, j, i] = pq.dequeue();
if (max - min < r - l) {
[l, r] = [min, max];
}
const iNext = i + 1;
if (iNext < nums[j].length) {
const next = nums[j][iNext];
pq.enqueue([next, j, iNext]);
max = Math.max(max, next);
}
}
return [l, r];
};
|
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 | const smallestRange = nums => {
const pq = new PriorityQueue((a, b) => a[0] - b[0]);
const n = nums.length;
let [l, r, max] = [0, Number.POSITIVE_INFINITY, Number.NEGATIVE_INFINITY];
for (let j = 0; j < n; j++) {
const x = nums[j][0];
pq.enqueue([x, j, 0]);
max = Math.max(max, x);
}
while (pq.size() === n) {
const [min, j, i] = pq.dequeue();
if (max - min < r - l) {
[l, r] = [min, max];
}
const iNext = i + 1;
if (iNext < nums[j].length) {
const next = nums[j][iNext];
pq.enqueue([next, j, iNext]);
max = Math.max(max, next);
}
}
return [l, r];
};
|