ধরুন আমাদের কাছে সাজানো পূর্ণসংখ্যার 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 এবং সংখ্যা[i, 0]
- এক জোড়া তাপমাত্রা সংজ্ঞায়িত করুন :=pq এর শীর্ষ
- pq থেকে উপাদান মুছুন
- tempMinRange :=temp.first
- idx :=তাপমাত্রার দ্বিতীয় উপাদান
- যদি tempMaxRange − tempMinRange
- রেঞ্জ সাইজ :=tempMaxRange - tempMinRange
- minRange :=tempMinRange
- maxRange :=tempMaxRange
- লুপ থেকে বেরিয়ে আসুন
- tempMaxRange :=সর্বোচ্চ tempMaxRange এবং সংখ্যা[idx, pointers[idx]]
- pq-এ { 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, ]