0786. K-th Smallest Prime Fraction ======================================================================================================================== 题目信息 -------- :题号: 0786 :难度: Medium :主题: 有序数组、分数排序、第 k 小 :原题: `LeetCode 0786 `_ :重点: 数组严格递增且由 1 和不同质数组成;只考虑 ``i < j`` 的分数 ``arr[i] / arr[j]``,按数值从小到大取第 ``k`` 个并返回其分子、分母 题目重述 -------- 给定一个严格递增的整数数组 ``arr``,其中第一个元素是 ``1``,其余元素都是互不相同的质数。对于每一对满足 ``0 <= i < j < arr.length`` 的下标,构造分数 ``arr[i] / arr[j]``。 将所有这些分数按数值从小到大排列,给定的 ``k`` 使用从 1 开始的排名。请返回第 ``k`` 小分数对应的 ``[分子, 分母]``。 ``2 <= arr.length <= 1000``,``1 <= arr[i] <= 3 * 10^4``,并且 ``1 <= k <= arr.length * (arr.length - 1) / 2``。 自建示例 -------- 比较不同分母产生的分数: .. code-block:: text 输入:arr = [1,2,5,11], k = 4 输出:[2,5] 解释:六个分数按从小到大排列为 1/11、2/11、1/5、2/5、5/11、1/2,因此第 4 小的是 2/5。 查询允许的最大排名: .. code-block:: text 输入:arr = [1,3,7], k = 3 输出:[3,7] 解释:三个候选分数按从小到大排列为 1/7、1/3、3/7。数组长度为 3 时共有 3 个候选,k = 3 取到允许的最大排名,因此返回最大的分数 3/7。