ภาพรวมปัญหา
สมมติว่ามีลิสต์ที่เรียงแล้ว มี 1 และจำนวนเฉพาะบางจำนวน สำหรับทุกคู่ p < q ในลิสต์ เราพิจารณาเศษส่วน p/q หาเศษส่วนที่เล็กที่สุดลำดับที่ k คืนค่าเป็นอาร์เรย์ [p, q]
ตัวอย่าง
A = [1, 3, 5, 7], k = 2 → เศษส่วนทั้งหมด: 1/3, 1/5, 1/7, 3/5, 3/7, 5/7 → เศษส่วนเล็กที่สุดลำดับ 2 คือ 1/5 → Output: [1, 5]
แนวทางแก้ปัญหา (Priority Queue / Min-Heap)
- ใช้ Min-Heap เก็บคู่ (ค่าเศษส่วน, ตัวเศษ, ตัวส่วน, index)
- เริ่มต้น push ทุกคู่ (A[0], A[i]) เข้า heap
- Pop k ครั้ง: ทุกครั้งที่ pop (a, b, idx) ให้ push (A[idx+1], b, idx+1) เข้า heap (ถ้ามี)
- ครั้งที่ k ที่ pop ได้คือคำตอบ
ตัวอย่างโปรแกรม
#include <bits/stdc++.h>
using namespace std;
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); // min-heap
}
};
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;
}
};
int main() {
Solution ob;
vector<int> v = {1, 3, 5, 7};
// print_vector(ob.kthSmallestPrimeFraction(v, 2));
}
Input
{1,3,5,7} 2
Output
[1, 5]
