मान लीजिए हमारे पास एक क्रमबद्ध सूची है, इसमें 1 और कुछ अभाज्य संख्याएं हैं, अब सूची में प्रत्येक 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 लेगा
- आकार 2 का एक ऐरे ret परिभाषित करें
- n := A का आकार
- एक प्रायोरिटी क्यू pq परिभाषित करें
- i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
- Data(A[0], A[i], 0) को pq में डालें
- जब K शून्येतर है, करें -
- temp = pq का शीर्ष तत्व
- pq से तत्व हटाएं
- यदि K, 0 के समान है, तो -
- ret[0] := temp का a
- ret[1] := temp का b
- ret वापस करें
- यदि temp.idx + 1 < n, तो -
- idx := temp का idx + 1
- Data(A[idx], temp.b, idx) को pq में डालें
- K को 1 से घटाएं
- 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, ]
