1. 题目链接
传送门:LeetCode 786. 第 K 个最小的素数分数
2. 题目描述
一个已排序好的表 A
,其包含 1 和其他一些素数. 当列表中的每一个 $p\lt q$ 时,我们可以构造一个分数 $p/q$ 。
那么第 k
个最小的分数是多少呢? 以整数数组的形式返回你的答案, 这里 answer[0] = p
且 answer[1] = q
.
1 | 示例: |
3. 解题思路
嵌套二分。首先二分分数值 $x$, 对于二分的每个 $x$,求解 $\mathcal S={(p,q))|\frac{p}{q}\lt x\mbox{ and }p\lt q }$ 的大小,通过比较集合与K的大小关系,找到第k小分数值。
计算 $|\mathcal S|$,也是通过二分来做。枚举分母 $q$,求数组中有多少个数小于等于 $x*q$。
复杂度 $\mathcal O(n\log n\log L)$。$L$ 是分数的数值表示范围。