0786. K-th Smallest Prime Fraction¶
题目信息¶
- 题号:
0786
- 难度:
Medium
- 主题:
有序数组、分数排序、第 k 小
- 原题:
- 重点:
数组严格递增且由 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。