C++のk個のリストから要素を含む最小範囲を検索します

k個の異なるリストがあるとします。要素が並べ替えられます。 k個の異なるリストのそれぞれから少なくとも1つの番号を含む最小範囲を検索する必要があります。ここで、範囲[a、b]は、b-a

したがって、入力が[[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

  • {nums [i、0]、i}をpq

    に挿入します

  • tempMaxRange：=tempMaxRangeとnums[i、0]の最大値

• 1がゼロ以外の場合、実行-

  • 1つのペアを定義しますtemp：=top of pq

  • pqから要素を削除する

  • tempMinRange：=temp.first

  • idx：=tempの2番目の要素

  • tempMaxRange --tempMinRange

    • rangeSize：=tempMaxRange --tempMinRange

    • minRange：=tempMinRange

    • maxRange：=tempMaxRange

  • （pointers [idx]を1増やします）

  • ポインタ[idx]がnums[idx]のサイズと同じである場合、-

    • ループから出てきます

  • それ以外の場合

    • tempMaxRange：=tempMaxRangeとnums[idx、pointers [idx]]

      の最大値

    • {nums [idx、pointers [idx]]、idx}をpq

      に挿入します

• サイズ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, ]