ধরুন আমাদের একটি সাজানো তালিকা আছে, সেখানে 1 এবং কিছু মৌলিক সংখ্যা আছে, এখন তালিকার প্রতিটি p
সুতরাং যদি ইনপুট হয় [1,3,5,7], এবং k =2, তাহলে উত্তর হবে 1/5, যেমন ভগ্নাংশগুলি 1/3, 1/5, 1/7, 3/5, 3/7, 5/7, দ্বিতীয় ক্ষুদ্রতম হল 1/5।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- ডেটা সংজ্ঞায়িত করুন, এতে a, b এবং/b লাগবে
- আকার 2 এর একটি অ্যারে রেট সংজ্ঞায়িত করুন
- n :=A এর আকার
- একটি অগ্রাধিকার সারি pq সংজ্ঞায়িত করুন
- আরম্ভ করার জন্য i :=0, যখন i
করুন - pq-এ ডেটা(A[0], A[i], 0) সন্নিবেশ করান
- temp =pq এর শীর্ষ উপাদান
- pq থেকে উপাদান মুছুন
- যদি K 0 এর সমান হয়, তাহলে −
- ret[0] :=a of temp
- ret[1] :=b of temp
- রিটার্ন রিটার্ন
- যদি temp.idx + 1
- idx :=temp + 1 এর idx
- pq-এ ডেটা (A[idx], temp.b, 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 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, ]