You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.
We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.
Example 1:
Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
Note:
- The given list may contain duplicates, so ascending order means >= here.
- 1 <=
k<= 3500 - -105 <=
value of elements<= 105. - For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.
这道题给了我们一些数组，都是排好序的，让我们求一个最小的范围，使得这个范围内至少会包括每个数组中的一个数字。虽然每个数组都是有序的，但是考虑到他们之间的数字差距可能很大，所以我们最好还是合并成一个数组统一处理比较好，但是合并成一个大数组还需要保留其原属数组的序号，所以我们大数组中存pair对，同时保存数字和原数组的序号。然后我们重新按照数字大小进行排序，这样我们的问题实际上就转换成了求一个最小窗口，使其能够同时包括所有数组中的至少一个数字。这不就变成了那道Minimum Window Substring。所以说啊，这些题目都是换汤不换药的，总能变成我们见过的类型。我们用两个指针left和right来确定滑动窗口的范围，我们还要用一个哈希表来建立每个数组与其数组中数字出现的个数之间的映射，变量cnt表示当前窗口中的数字覆盖了几个数组，diff为窗口的大小，我们让right向右滑动，然后判断如果right指向的数字所在数组没有被覆盖到，cnt自增1，然后哈希表中对应的数组出现次数自增1，然后我们循环判断如果cnt此时为k(数组的个数)且left不大于right，那么我们用当前窗口的范围来更新结果，然后此时我们想缩小窗口，通过将left向右移，移动之前需要减小哈希表中的映射值，因为我们去除了数字，如果此时映射值为0了，说明我们有个数组无法覆盖到了，cnt就要自减1。这样遍历后我们就能得到最小的范围了，参见代码如下：
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
vector<int> res;
vector<pair<int, int>> v;
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); ++i) {
for (int num : nums[i]) {
v.push_back({num, i});
}
}
sort(v.begin(), v.end());
int left = 0, n = v.size(), k = nums.size(), cnt = 0, diff = INT_MAX;
for (int right = 0; right < n; ++right) {
if (m[v[right].second] == 0) ++cnt;
++m[v[right].second];
while (cnt == k && left <= right) {
if (diff > v[right].first - v[left].first) {
diff = v[right].first - v[left].first;
res = {v[left].first, v[right].first};
}
if (--m[v[left].second] == 0) --cnt;
++left;
}
}
return res;
}
};
类似题目：
参考资料：