資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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 不為零時，執行：
- temp = pq 的頂部元素
- 從 pq 中刪除元素
- 如果 K 等於 0，則：
- ret[0] := temp 的 a
- ret[1] := temp 的 b
- 返回 ret
- 如果 temp.idx + 1 < n，則：
- idx := temp 的 idx + 1
- 將 Data(A[idx], temp.b, idx) 插入到 pq 中
- 將 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, ]
更新於： 2020年6月2日
449 次檢視
廣告