C ++中第K个最小素数
假设我们有一个排序的列表，有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。
为了解决这个问题，我们将遵循以下步骤-
定义数据，这将需要a，b和a/b
定义大小为2的数组ret
n：=A的大小
定义一个优先级队列pq
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
将Data（A[0]，A[i]，0）插入pq
当K不为零时，执行-
idx：=临时IDx+1
将Data（A[idx]，temp.b，idx）插入pq
ret[0]：=温度的a
ret[1]：=b的温度
返回ret
temp=pq的顶部元素
从pq中删除元素
如果K等于0，则-
如果temp.idx+1<n，则-
将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, ]