力扣每日一题2021-11-29第k个最小的素数分数

• 786.第k个最小的素数分数
• • 题目描述
  • 思路
  • • 二分查找+双指针
    • • Python实现
      • Java实现

第k个最小的素数分数

可以猜测一个实数α，如果恰好有k个素数分数小于α，则k个素数分数中最大的就是第k个最小的素数分数。
对于α，可以使用双指针来求值：

• 使用指针j指向分母，这个指针每次向右移动一个位置，用于枚举不同的分母；
• 使用指针i指向分子，这个指针不断向右移动，并且确保 a r r [ i ] / a r r [ j ] < α arr[i]/arr[j] < α arr[i]/arr[j]<α成立。当指针i无法移动时，就知道arr[0]、…、arr[i]都可以满足该式子，而arr[i+1]及之后的元素都不行。所以分母为arr[j]时，小于α的素数分数有i+1个。
• 在j向右移动时，把每个j对应的i+1加入计算结果，在双指针的过程完成后，就可以知道有多少个小于α的分数。
  如果得到的结果恰好为k，则计算出所有arr[i]/arr[j]的最大值即可。如果结果小于k，则α太小，增加它的值。如果结果大于k，则α太大，减小它的值。
  因此，可以使用二分查找来获取α的值，上界为1，下界为0，取中点为α，计算小于α的素数分数的个数，并根据这个值来调整二分查找的上下界。

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        n = len(arr)
        left, right = 0.0, 1.0
        while True:
            mid = (left + right) / 2
            i, count = -1, 0
            x, y = 0, 1
            for j in range(1, n):
                while arr[i+1] / arr[j] < mid:
                    i += 1
                    if arr[i] * y > arr[j] * x:
                        x, y = arr[i], arr[j]
                count += i + 1
            if count == k:
                return [x, y]
            if count < k:
                left = mid
            else:
                right = mid

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        double left = 0.0, right = 1.0;
        while (true) {
            double mid = (left + right) / 2;
            int i = -1, count = 0;
            int x = 0, y = 1;
            for (int j = 1; j < n; ++j) {
                while ((double) arr[i+1] / arr[j] < mid) {
                    ++i;
                    if (arr[i] * y > arr[j] * x) {
                        x = arr[i];
                        y = arr[j];
                    }
                }
                count += i + 1;
            }
            if (count == k) {
                return new int[] {x, y};
            }
            if (count < k) {
                left = mid;
            } else {
                right = mid;
            }
        }
    }
}