Java实现 LeetCode 786 第 K 个最小的素数分数(大小堆)
2024-08-31 11:20:31
786. 第 K 个最小的素数分数
一个已排序好的表 A,其包含 1 和其他一些素数. 当列表中的每一个 p<q 时,我们可以构造一个分数 p/q 。
那么第 k 个最小的分数是多少呢? 以整数数组的形式返回你的答案, 这里 answer[0] = p 且 answer[1] = q.
示例:
输入: A = [1, 2, 3, 5], K = 3
输出: [2, 5]
解释:
已构造好的分数,排序后如下所示:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3.
很明显第三个最小的分数是 2/5.
输入: A = [1, 7], K = 1
输出: [1, 7]
注意:
A 长度的取值范围在 2 — 2000.
每个 A[i] 的值在 1 —30000.
K 取值范围为 1 —A.length * (A.length - 1) / 2
PS:
因为求出来的都是小于1的,我们直接按照值得范围去查找
大小堆主要是分堆得时候不好分
class Solution {
public int[] kthSmallestPrimeFraction(int[] A, int K) {
if (null == A || A.length <= 0) return A;
double lo = 0, hi = 1;
int[] ans = new int[2];
while (lo <= hi) {
double mid = lo + (hi - lo) / 2;
int[] finds = findKthFraction(A, mid);
if (finds[0] < K)
lo = mid;
else if (finds[0] > K)
hi = mid;
else {
ans[0] = finds[1];
ans[1] = finds[2];
return ans;
}
}
return ans;
}
private int[] findKthFraction(int[] fraction, double x) {
int p = 0, q = 1, count = 0, i = -1; //p 分子 q 分母
for (int j = 1; j < fraction.length; ++j) {
//这里的筛选是,按照指定的值的范围去寻找,本来是fra[i+1]/fra[j]<x
while (i < fraction.length && fraction[i + 1] < fraction[j] * x) ++i;
count += i + 1;
// A / B - C / D = A * D / B * D - C * B / B * D;
//=> A * D - B * C
if (i >= 0 && p * fraction[j] < q * fraction[i]) {
p = fraction[i];
q = fraction[j];
}
}
return new int[]{count, p, q};
}
}
最新文章
- [转载]存储基础:DAS/NAS/SAN存储类型及应用
- C# WebSocket 服务端示例代码 + HTML5客户端示例代码
- homework-Agile Software Development
- WPF画N角芒星,正N角星
- hdu 4709 Herding hdu 2013 热身赛
- js怎样推断一个对象{}是否为空对象,没有不论什么属性
- c#之循环效率
- Tomcat针对网站打开速度慢进行局部优化方案
- “蝉原则”与CSS3随机多背景随机圆角等效果
- Golang 知识点总结
- 英语口语练习系列-C18-Wildest Dreams
- Linux系统安装IonCube的方法详解教程
- LA 6893 矩阵HASH (模板)
- Linux shell ftp命令下载文件 根据文件日期
- 基本数据类型、包装类、String之间的转换
- MVC批量添加,增加一条记录的同时添加N条集合属性所对应的个体
- VB调用VC dll的返回方式
- atom插件安装引发的nodejs和npm安装血案
- 正则表达式:Python 模块 re 简介
- vim配置总结