C ++中来自K列表的最小范围覆盖元素
假设我们有k个排序的整数列表。我们必须从k个列表中的每个列表中搜索包含至少一个数字的最小范围。当ba<dc时，范围[a，b]小于范围[c，d]；如果ba==dc，则范围a<c。
因此，如果输入类似于[[4,10,15,25,26]，[0,9,14,20]，[5,18,24,30]]，则输出将为[14，18]
为了解决这个问题，我们将遵循以下步骤-
minRange：=inf，maxRange：=-inf，rangeSize：=inf，tempMinRange：=inf，tempMaxRange：=-inf
n：=nums的大小
定义大小为n的数组指针
使优先级队列pq
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
将{nums[i，0]，i}插入pq
tempMaxRange：=tempMaxRange和nums[i，0]的最大值
当1不为零时，执行-
tempMaxRange：=tempMaxRange和nums[idx，指针[idx]]的最大值
将{nums[idx，pointers[idx]]，idx}插入pq
从循环中出来
rangeSize：=tempMaxRange-tempMinRange
minRange：=tempMinRange
maxRange：=tempMaxRange
定义一对temp：=pq的顶部
从pq中删除元素
tempMinRange：=温度第一
idx：=temp的第二个元素
如果tempMaxRange-tempMinRange<rangeSize，则-
（将指标[idx]增加1）
如果pointerss[idx]与nums[idx]的大小相同，则-
除此以外
定义大小为2的数组
ans[0]：=minRange，ans[1]：=maxRange
返回ans
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
struct Comparator{
bool operator() (pair <int, int> a, pair <int, int> b){
return !(a.first < b.first);
}
};
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int minRange = INT_MAX;
int maxRange = INT_MIN;
int rangeSize = INT_MAX;
int tempMinRange, tempMaxRange, tempRangeSize;
tempMinRange = INT_MAX;
tempMaxRange = INT_MIN;
int n = nums.size();
vector <int> pointers(n);
priority_queue < pair <int, int>, vector < pair <int, int> >, Comparator > pq;
for(int i = 0; i < n; i++){
pq.push({nums[i][0], i});
tempMaxRange = max(tempMaxRange, nums[i][0]);
}
while(1){
pair <int, int> temp = pq.top();
pq.pop();
tempMinRange = temp.first;
int idx = temp.second;
if(tempMaxRange - tempMinRange < rangeSize){
rangeSize = tempMaxRange - tempMinRange;
minRange = tempMinRange;
maxRange = tempMaxRange;
}
pointers[idx]++;
if(pointers[idx] == nums[idx].size())break;
else{
tempMaxRange = max(tempMaxRange, nums[idx][pointers[idx]]);
pq.push({nums[idx][pointers[idx]], idx});
}
}
vector <int> ans(2);
ans[0] = minRange;
ans[1] = maxRange;
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{4,10,15,25,26},{0,9,14,20},{5,18,24,30}};
print_vector(ob.smallestRange(v));
}输入项
{{4,10,15,25,26},{0,9,14,20},{5,18,24,30}};输出结果
[14, 18, ]