मान लीजिए हमारे पास k अलग-अलग लिस्ट्स हैं। तत्व सॉर्टेड हैं। हमें सबसे छोटी रेंज खोजनी है जिसमें k अलग-अलग लिस्ट्स में से प्रत्येक से कम से कम एक संख्या शामिल हो। यहां रेंज [a,b] रेंज [c,d] से छोटी है जब b-a < d-c या a < c यदि b-a == d-c।
उदाहरण के लिए, यदि इनपुट [[4,10,15,25,26],[0,9,14,20],[5,18,24,30]] है, तो आउटपुट [14, 18] होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- मिनरेंज := inf, मैक्सरेंज := -inf, रेंजसाइज := inf, टेम्पमिनरेंज := inf, टेम्पमैक्सरेंज := -inf
- n := nums का आकार
- आकार n का एक ऐरे पॉइंटर्स परिभाषित करें
- एक प्रायोरिटी क्यू pq बनाएं
- i := 0 से n-1 तक लूप करें:
- { nums[i][0], i } को pq में डालें
- टेम्पमैक्सरेंज := टेम्पमैक्सरेंज और nums[i][0] का अधिकतम
- जब तक 1 शून्येतर है:
- टेम्प := pq का शीर्ष परिभाषित करें
- pq से तत्व हटाएं
- टेम्पमिनरेंज := टेम्प.फर्स्ट
- इंडेक्स := टेम्प.सेकंड
- यदि टेम्पमैक्सरेंज - टेम्पमिनरेंज < रेंजसाइज: रेंजसाइज, मिनरेंज, मैक्सरेंज अपडेट करें
- पॉइंटर्स[इंडेक्स] बढ़ाएं
- यदि पॉइंटर्स[इंडेक्स] nums[इंडेक्स] के आकार के बराबर है, तो लूप से बाहर निकलें
- अन्यथा:
- टेम्पमैक्सरेंज := टेम्पमैक्सरेंज और nums[इंडेक्स][पॉइंटर्स[इंडेक्स]] का अधिकतम
- { nums[इंडेक्स][पॉइंटर्स[इंडेक्स]], इंडेक्स } को pq में डालें
- आकार 2 का एक ऐरे ans परिभाषित करें
- ans[0] := मिनरेंज, ans[1] := मैक्सरेंज
- 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, ]