第 K 个最小的质数分数

难度: Medium

给你一个按递增顺序排序的数组 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 <= 1000
1 <= arr[i] <= 3 * 10⁴
arr[0] == 1
arr[i] 是一个质数，i > 0
arr 中的所有数字 互不相同 ，且按 严格递增 排序
1 <= k <= arr.length * (arr.length - 1) / 2

进阶：你可以设计并实现时间复杂度小于 O(n²) 的算法解决此问题吗？

Submission

运行时间: 51 ms

内存: 16.1 MB

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        n = len(arr)
        left = 0
        right = 1.0

        while True:
            mid = (left + right) / 2
            i, count = -1, 0 # i 为分子
            x, y = 0, 1 # 记录最大值

            for j in range(1, n): # 列举分母
                while arr[i+1] / arr[j] < mid:
                    i += 1
                    if arr[i] /  arr[j] >  x / y:
                        x, y = arr[i], arr[j]
                count += i + 1
            
            if count == k:
                return [x, y]
            
            if count < k:
                left = mid
            else:
                right = mid

Explain

该题解使用二分查找的思路。首先将查找范围设为 [0, 1]，因为分数的取值范围在 0 到 1 之间。然后在每次二分查找时，统计小于等于 mid 的分数个数 count。如果 count 等于 k，说明找到了第 k 小的分数；如果 count 小于 k，说明第 k 小的分数在 (mid, right] 范围内，缩小查找范围为 [mid, right]；如果 count 大于 k，说明第 k 小的分数在 [left, mid) 范围内，缩小查找范围为 [left, mid]。在统计 count 的过程中，使用双指针分别指向分子和分母，并记录最大的分数。

时间复杂度: O(nlog(1/eps))

空间复杂度: O(1)

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        n = len(arr)
        left = 0
        right = 1.0

        while True:
            mid = (left + right) / 2
            i, count = -1, 0 # i 为分子
            x, y = 0, 1 # 记录最大值

            for j in range(1, n): # 列举分母
                while arr[i+1] / arr[j] < mid:
                    i += 1
                    if arr[i] /  arr[j] >  x / y:
                        x, y = arr[i], arr[j]
                count += i + 1
            
            if count == k:
                return [x, y]
            
            if count < k:
                left = mid
            else:
                right = mid

Explore

由于`arr`数组中的元素都是质数，且分数的形式为arr[i]/arr[j] (i < j)，这意味着所有可能的分数的值必定在0到1之间。最小的可能值0可以通过一个非常小的数除以一个非常大的数趋近得到（虽然实际上不会出现这种分数），而最大的可能值1是通过任何数除以其自身得到。因此，[0,1]是一个合理的初始化范围，能覆盖所有可能的分数值。

在题解的实现中，二分查找的终止条件是在找到恰好的第k小的分数时。由于每次迭代都会将搜索区间减半，因此会逐渐接近真正的第k小的分数值。虽然题解中没有明确的退出while循环的条件，实际实现时通常会设置一个足够小的阈值(例如epsilon)，当right和left的差值小于这个阈值时，可以认为已经足够接近答案，此时可以终止循环。

双指针方法有效的原因在于它能高效地遍历所有的分数并计数。其中一个指针固定分母，另一个指针遍历可能的分子，从而快速统计出小于等于mid的分数个数。这种方法假设数组`arr`是有序的，因此能保证分数是递增的，从而使双指针方法有效。潜在的限制包括对数组的排序（如果原始数组未排序），以及在某些情况下可能会因为过多的相同比值的分数而导致计数复杂化。

这里的“最大的分数”指的是在当前二分查找的mid值下，小于等于mid的所有分数中最接近mid的那个分数。随着二分查找的进行，我们需要不断更新这个“最接近mid的最大分数”，以便当找到恰好有k个分数小于某个mid时，能够返回这个最接近的分数。因此，这并不矛盾，而是为了确保能返回最接近真实第k小分数的值，这个过程是对结果的一种优化和精确控制。