C++에서 K번째로 작은 소수

하나의 정렬된 목록이 있고 1과 소수의 소수가 있다고 가정합니다. 이제 목록의 모든 p

따라서 입력이 [1,3,5,7]이고 k =2인 경우 분수는 1/3, 1/5, 1/7, 3/5이므로 답은 1/5가 됩니다. 3/7, 5/7, 두 번째로 작은 값은 1/5입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 데이터 정의, b 및 a/b 소요
• 크기 2의 배열 ret 정의
• n :=A의 크기
• 하나의 우선순위 큐 pq 정의
• 초기화 i의 경우:=0, i
• 데이터(A[0], A[i], 0)를 pq에 삽입

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

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