मान लीजिए कि हमारे पास क्रमबद्ध पूर्णांकों की 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
करें - पीक्यू में {nums[i, 0], i } डालें
- tempMaxRange :=अधिकतम tempMaxRange और nums[i, 0]
- एक जोड़ी अस्थायी परिभाषित करें:=pq के शीर्ष
- पीक्यू से तत्व हटाएं
- tempMinRange :=temp.first
- idx:=अस्थायी का दूसरा तत्व
- यदि tempMaxRange − tempMinRange
- श्रेणी आकार:=tempMaxRange - tempMinRange
- minRange:=tempMinRange
- अधिकतम श्रेणी:=tempMaxRange
- लूप से बाहर आएं
- tempMaxRange :=अधिकतम tempMaxRange और nums[idx, पॉइंटर्स[idx]]
- पीक्यू में {nums[idx,pointers[idx]], idx } डालें
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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, ]