题目简介：
你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
示例 1:
1
2
3
4
5
6
| 输入:[[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] 中。
|
注意:
- 给定的列表可能包含重复元素，所以在这里升序表示 >= 。
- 1 <=
k <= 3500
- -105 <=
元素的值 <= 105
思路：
这题与 76. 最小覆盖子串 的解题方法是差不多的，都是用哈希表+滑动窗口。
首先初始化哈希表，将元素的值及其所在的列表下标存入哈希表中。并在过程中保存所有元素的最大值和最小值作为边界值。
初始化right = left = Min，并且右边界开始右移扩大窗口，当map[right]存在时，将其对应的列表下标count[map[right][i]]++，当count[map[right][i]] == 1时，说明该列表刚有一个元素位于目前的区间中，sum++。
当sum == num.size()时，说明目前的区间已符合答案要求，尝试缩小区间并不断更新答案区间。
缩小区间时，左边界不断右移，直至sum != nums.size()，当map[left]存在时，将其对应的列表下标count[map[left][i]]--，当count[map[left][i]] == 0时，说明该列表没有元素位于目前的区间中，sum--。
最后当right > Max时跳出循环，最后返回{res_left, res_right}即可。
tip:
代码如下：
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
| class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
unordered_map<int, vector<int>> map;
int Max = INT_MIN;
int Min = INT_MAX;
for(int i = 0; i < nums.size(); i++){
for(int j = 0; j < nums[i].size(); j++){
map[nums[i][j]].push_back(i);
Max = max(Max, nums[i][j]);
Min = min(Min, nums[i][j]);
}
}
int left = Min;
int right = Min;
int res_left = Min;
int res_right = Max;
int sum = 0;
vector<int> count(nums.size(), 0);
while(right <= Max){
if(map.count(right)){
for(int i = 0; i < map[right].size(); i++){
count[map[right][i]]++;
if(count[map[right][i]] == 1)
sum++;
}
}
while(sum == nums.size()){
if(right - left < res_right - res_left){
res_left = left;
res_right = right;
}
if(map.count(left)){
for(int i = 0; i < map[left].size(); i++){
count[map[left][i]]--;
if(count[map[left][i]] == 0)
sum--;
}
}
left++;
}
right++;
}
return {res_left, res_right};
}
};
|
