leetcode786.第k个最小的素数分数
1.题目描述
一个已排序好的表 A,其包含 1 和其他一些素数. 当列表中的每一个 p<q 时,我们可以构造一个分数 p/q 。
那么第 k 个最小的分数是多少呢? 以整数数组的形式返回你的答案, 这里 answer[0] = p 且 answer[1] = q.
示例:
输入: A = [1, 2, 3, 5], K = 3
输出: [2, 5]
解释:
已构造好的分数,排序后如下所示:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3.
很明显第三个最小的分数是 2/5.
输入: A = [1, 7], K = 1
输出: [1, 7]
注意:
A 的取值范围在 2 — 2000.
每个 A[i] 的值在 1 —30000.
K 取值范围为 1 —A.length * (A.length - 1) / 2
2.解题思路
- 二分查找:
初始值:mid =(0.0+1.0)/2,
如果小于mid值的分数的个数 < K:去mid右侧查找,left=mid
如果小于mid值的分数的个数 > K:去mid左侧查找,right=mid
如果小于mid值的分数的个数 = K:则位于mid之前的最大的分数即为所求(最接近mid的真分数)
- 那如何表示一个分数并且找到小于mid值得分数的个数呢?
设 0<= j < i < N,则p = A[j],q = A[i]分别表示分子、分母(题中要求分子p<分母q)。固定分母q =A[i] ,j越大,此分数的值越大那么就可以利用此规律,快速的找出比mid小的分数有多少个。
- 那如何表示mid之前的最大的分数呢?
设置变量cureps,表示离mid与离mid最近的真分数的差值,差值越小,说明离mid越近,并不断更新 p = A[j-1],q = A[i],j代表的是第一个大于mid的 A[j] / A[i],所以小于等于mid的是前面的一个元素,最后返回 p , q
如果j无法向前移动(j = 0),说明当前分母q =A[i]不合适,任意一个分子都不能是真分数小于mid,则i++
3.代码实现
class Solution(object):
def kthSmallestPrimeFraction(self, A, K):
"""
:type A: List[int]
:type K: int
:rtype: List[int]
"""
n = len(A)
left = 0.0
right = 1.0
count = 0
p = 0
q = 0
while left<right:
mid = (left + right) / 2
count = 0
eps = 1.0
for i in range(1, n):
j=0
while j<i:
# 除法变乘法,加速
if A[j] <= mid*A[i]:
count += 1
else:
#大于的mid不需要往下看了,随着j++,后面只会越来越大
break
j+=1
# j代表的是第一个大于mid的A[j]/A[i],所以小于等于mid的是前面的一个元素
# 如果j=0,说明以A[i]作分母时,没有分子能够符合条件
# 求解最接近mid的真分数
if j > 0:
cureps = mid - float(A[j - 1]) / (A[i])
if cureps > 0 and cureps < eps:
p = j - 1
q = i
eps = cureps
if count < K:
left = mid
elif count > K:
right = mid
else:
return A[p], A[q]
return A[p], A[q]
4.运行结果
很奇怪,leetcode有时能通过,有时又不能。
上一篇: 二分查找法(递归与非递归方式)