leetcode在力扣 App 中打开
调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
中等
相关标签
相关企业

给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr1 和若干 质数 组成,且其中所有整数互不相同。

对于每对满足 0 <= i < j < arr.lengthij ,可以得到分数 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 * 104
  • arr[0] == 1
  • arr[i] 是一个 质数i > 0
  • arr 中的所有数字 互不相同 ,且按 严格递增 排序
  • 1 <= k <= arr.length * (arr.length - 1) / 2

 

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

通过次数
37.5K
提交次数
55.1K
通过率
67.9%


相关企业


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
arr =
[1,2,3,5]
k =
3
Source