C ++中来自K列表的最小范围覆盖元素

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有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, ]

    以上是 C ++中来自K列表的最小范围覆盖元素 的全部内容， 来源链接： utcz.com/z/316671.html

    回到顶部