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。

自建示例

比较不同分母产生的分数:

输入:arr = [1,2,5,11], k = 4
输出:[2,5]
解释:六个分数按从小到大排列为 1/11、2/11、1/5、2/5、5/11、1/2,因此第 4 小的是 2/5。

查询允许的最大排名:

输入:arr = [1,3,7], k = 3
输出:[3,7]
解释:三个候选分数按从小到大排列为 1/7、1/3、3/7。数组长度为 3 时共有 3 个候选,k = 3 取到允许的最大排名,因此返回最大的分数 3/7。