欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode786.第k个最小的素数分数

程序员文章站 2022-06-17 19:46:04
...

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.运行结果

leetcode786.第k个最小的素数分数

很奇怪,leetcode有时能通过,有时又不能。