数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告