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, ]