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, ]