Description
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>. And after you reset the code template, you'll see this point.
这道题给了我们一些数组，都是排好序的，让求一个最小的范围，使得这个范围内至少会包括每个数组中的一个数字。虽然每个数组都是有序的，但是考虑到他们之间的数字差距可能很大，所以最好还是合并成一个数组统一处理比较好，但是合并成一个大数组还需要保留其原属数组的序号，所以大数组中存pair对，同时保存数字和原数组的序号。然后重新按照数字大小进行排序，这样问题实际上就转换成了求一个最小窗口，使其能够同时包括所有数组中的至少一个数字。这不就变成了那道 Minimum Window Substring。所以说啊，这些题目都是换汤不换药的，总能变成我们见过的类型。这里用两个指针 left 和 right 来确���滑动窗口的范围，还要用一个 HashMap 来建立每个数组与其数组中数字出现的个数之间的映射，变量 cnt 表示当前窗口中的数字覆盖了几个数组，diff 为窗口的大小，让 right 向右滑动，然后判断如果 right 指向的数字所在数组没有被覆盖到，cnt 自增1，然后 HashMap 中对应的数组出现次数自增1，然后循环判断如果 cnt 此时为k(数组的个数)且 left 不大于 right，那么用当前窗口的范围来更新结果，然后此时想缩小窗口，通过将 left 向右移，移动之前需要减小 HashMap 中的映射值，因为去除了数字，如果此时映射值为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;
}
};
这道题还有一种使用 priority_queue 来做的，优先队列默认情况是最大堆，但是这道题我们需要使用最小堆，重新写一下 comparator 就行了。解题的主要思路很上面的解法很相似，只是具体的数据结构的使用上略有不同，这 curMax 表示当前遇到的最大数字，用一个 idx 数组表示每个 list 中遍历到的位置，然后优先队列里面放一个pair，是数字和其所属list组成的对儿。遍历所有的list，将每个 list 的首元素和该 list 序号组成 pair 放入队列中，然后 idx 数组中每个位置都赋值为1，因为0的位置已经放入队列了，所以指针向后移一个位置，还要更新当前最大值 curMax。此时 queue 中是每个 list 各有一个数字，由于是最小堆，所以最小的数字就在队首，再加上最大值 curMax，就可以初始化结果 res 了。然后进行循环，注意这里循环的条件不是队列不为空，而是当某个 list 的数字遍历完了就结��循环，因为范围要 cover 每个 list 至少一个数字。所以 while 循环条件即是队首数字所在的 list 的遍历位置小于该 list 的总个数，在循环中，取出队首数字所在的 list 序号t，然后将该 list 中下一个位置的数字和该 list 序号t组成 pair，加入队列中，然后用这个数字更新 curMax，同时 idx 中t对应的位置也自增1。现在来更新结果 res，如果结果 res 中两数之差大于 curMax 和队首数字之差，则更新结果 res，参见代码如下：
解法二：
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int curMax = INT_MIN, n = nums.size();
vector<int> idx(n, 0);
auto cmp = [](pair<int, int>& a, pair<int, int>& b) {return a.first > b.first;};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp) > q(cmp);
for (int i = 0; i < n; ++i) {
q.push({nums[i][0], i});
idx[i] = 1;
curMax = max(curMax, nums[i][0]);
}
vector<int> res{q.top().first, curMax};
while (idx[q.top().second] < nums[q.top().second].size()) {
int t = q.top().second; q.pop();
q.push({nums[t][idx[t]], t});
curMax = max(curMax, nums[t][idx[t]]);
++idx[t];
if (res[1] - res[0] > curMax - q.top().first) {
res = {q.top().first, curMax};
}
}
return res;
}
};
Github 同步地址：
类似题目：
参考资料：
https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/
https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/discuss/104886/Clean-C%2B%2B-priority_queue-solution-using-iterators