LeetCode 题解工作台
第 K 个最小的质数分数
给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 质数 组成，且其中所有整数互不相同。 对于每对满足 0 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。 那么第 k 个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里 answ…
5
题型
4
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
class Solution: def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 质数 组成，且其中所有整数互不相同。
对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。
那么第 k 个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。
示例 1：
输入：arr = [1,2,3,5], k = 3 输出：[2,5] 解释：已构造好的分数,排序后如下所示: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3 很明显第三个最小的分数是 2/5
示例 2：
输入：arr = [1,7], k = 1 输出：[1,7]
提示：
2 <= arr.length <= 10001 <= arr[i] <= 3 * 104arr[0] == 1arr[i]是一个 质数 ，i > 0arr中的所有数字 互不相同 ，且按 严格递增 排序1 <= k <= arr.length * (arr.length - 1) / 2
进阶：你可以设计并实现时间复杂度小于 O(n2) 的算法解决此问题吗？
解题思路
方法一
class Solution:
def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
h = [(1 / y, 0, j + 1) for j, y in enumerate(arr[1:])]
heapify(h)
for _ in range(k - 1):
_, i, j = heappop(h)
if i + 1 < j:
heappush(h, (arr[i + 1] / arr[j], i + 1, j))
return [arr[h[0][1]], arr[h[0][2]]]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O((n + k) * log n) due to binary search iterations and counting with two pointers. Space complexity is O(n) for heap or pointer tracking arrays. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Asks about efficient fraction counting instead of brute force enumeration.
- question_mark
Hints at using binary search over the value range rather than array indices.
- question_mark
Watches for careful handling of duplicate numerator-denominator pairs and floating-point comparisons.
常见陷阱
外企场景- error
Generating all n*(n-1)/2 fractions causes TLE for large arrays.
- error
Failing to properly maintain two pointers while counting fractions below the midpoint.
- error
Incorrect floating-point comparisons leading to off-by-one fraction selection.
进阶变体
外企场景- arrow_right_alt
Find the k-th largest fraction instead of smallest using the same binary search approach.
- arrow_right_alt
Compute fractions only for a subset of the array with specific numerator or denominator constraints.
- arrow_right_alt
Return all fractions less than a given threshold using a similar heap or two-pointer counting method.