C++ में k सूचियों से तत्वों वाली सबसे छोटी श्रेणी खोजें

मान लीजिए कि हमारे पास k अलग-अलग सूचियाँ हैं। तत्वों को क्रमबद्ध किया जाता है। हमें सबसे छोटी श्रेणी खोजनी है जिसमें प्रत्येक k विभिन्न सूचियों में से कम से कम एक संख्या शामिल हो। यहाँ रेंज [a,b] रेंज [c,d] से छोटी है जब 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 :=अंकों का आकार

• आकार n के सरणी पॉइंटर्स को परिभाषित करें

• प्राथमिकता कतार बनाएं pq

• इनिशियलाइज़ i:=0 के लिए, जब i

  • pq में { nums[i, 0], i } डालें

  • tempMaxRange :=अधिकतम tempMaxRange और nums[i, 0]

• जबकि 1 शून्य नहीं है, करें -

  • एक जोड़ी अस्थायी परिभाषित करें:=pq के ऊपर

  • pq से तत्व हटाएं

  • tempMinRange :=temp.first

  • idx:=अस्थायी का दूसरा तत्व

  • अगर tempMaxRange - tempMinRange

    • रेंज साइज:=टेम्पमैक्स रेंज - टेम्पमिन रेंज

    • मिनरेंज:=टेम्पमिनरेंज

    • मैक्स रेंज:=टेम्पमैक्स रेंज

  • (पॉइंटर्स [idx] को 1 से बढ़ाएं)

  • अगर पॉइंटर्स [idx] अंकों के आकार [idx] के समान है, तो -

    • लूप से बाहर आएं

  • अन्यथा

    • tempMaxRange :=अधिकतम tempMaxRange और nums[idx, पॉइंटर्स[idx]]

    • pq में {nums[idx, पॉइंटर्स[idx]], idx} डालें

• आकार 2 के एक सरणी उत्तर को परिभाषित करें

• ans[0] :=minRange, ans[1] :=maxRange

• वापसी उत्तर

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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