하나의 정렬된 목록이 있고 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에 삽입
- temp =pq의 최상위 요소
- pq에서 요소 삭제
- K가 0과 같으면 -
- ret[0] :=온도
- ret[1] :=온도의 b
- 반환
- temp.idx + 1
- idx :=임시 idx + 1
- 데이터(A[idx], temp.b, idx)를 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, ]