মনে করুন, একটি সোর্টেড লিস্ট আছে যেখানে ১ এবং কিছু প্রাইম সংখ্যা রয়েছে। এখন লিস্টের প্রতিটি p < q জোড়ার জন্য p/q ভগ্নাংশ বিবেচনা করলে, k-তম ক্ষুদ্রতম ভগ্নাংশটি কোটি তা বের করতে হবে। উত্তরটি একটি অ্যারে হিসেবে রিটার্ন করতে হবে, যেখানে ans[0] = p এবং ans[1] = q।
যেমন, ইনপুট [1,3,5,7] এবং k = 2 হলে, উত্তর হবে 1/5। কারণ ভগ্নাংশগুলো হলো 1/3, 1/5, 1/7, 3/5, 3/7, 5/7, जिनमें দ্বিতীয় ক্ষুদ্রতম হলো 1/5।
সমাধানের ধাপসমূহ
- Data স্ট্রাকচার সংজ্ঞায়িত করুন যা a, b এবং a/b ধারণ করবে
- সাইজ ২-এর একটি ret অ্যারে সংজ্ঞায়িত করুন
- n := A.size()
- একটি প্রায়োরিটি কিউ pq সংজ্ঞায়িত করুন
- i := 0 থেকে n-1 পর্যন্ত: pq-তে Data(A[0], A[i], 0) ঢুকান
- যখন K != 0
- temp := pq.top(), pq.pop()
- যদি K == 0 হয়, ret[0] := temp.a, ret[1] := temp.b, ret রিটার্ন করুন
- যদি temp.idx + 1 < n হয়, idx := temp.idx + 1, pq-তে Data(A[idx], temp.b, idx) ঢুকান
- K কমান
- ret রিটার্ন করুন
উদাহরণ
#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 Data{ double val, a, b; int idx; Data(double a, double b, int c){ val = a / b; this->a = a; this->b = b; idx = c; } }; struct Comparator{ bool operator()(Data a, Data b){ return !(a.val < b.val); } }; class Solution { public: vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) { vector <int> ret(2); int n = A.size(); priority_queue <Data, vector <Data>, Comparator> pq; for(int i = 0; i < n; i++){ pq.push(Data(double(A[0]), double(A[i]), 0)); } while(K--){ Data temp = pq.top(); pq.pop(); if(K == 0){ ret[0] = temp.a; ret[1] = temp.b; return ret; } if(temp.idx + 1 < n){ int idx = temp.idx + 1; pq.push(Data(double(A[idx]), double(temp.b), idx)); } } return ret; } }; main(){ Solution ob; vector<int> v = {1,3,5,7}; print_vector(ob.kthSmallestPrimeFraction(v, 2)); }
ইনপুট
{1,3,5,7} 2
আউটপুট
[1, 5, ]
