786. 第 K 个最小的素数分数

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

对于每对满足 0 < i < j < arr.length 的 i 和 j ，可以得到分数 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]

解法一：指定规则排序

  1. class Solution:
  2.     def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
  3.         def cmp(x: Tuple[int, int], y: Tuple[int, int]) -> int:
  4.             return -1 if x[0] * y[1] < x[1] * y[0] else 1
  5.         n = len(arr)
  6.         ans = list()
  7.         for i in range(n):
  8.             for j in range(i+1, n):
  9.                 ans.append((arr[i], arr[j]))
  10.         # 自定义排序规则
  11.         ans.sort(key=(cmp_to_key(cmp)))
  12.         return list(ans[k-1])

时间复杂度：O(n n log n)，空间复杂度：O(n * n)

解法二：二分查找+双指针

  1. class Solution:
  2.     def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
  3.         n = len(arr)
  4.         left, right = 0.0, 1.0
  5.         while True:
  6.             mid = (left + right) / 2
  7.             i, count = -1, 0
  8.             x, y = 0, 1
  9.             for j in range(1, n):
  10.                 while arr[i+1] / arr[j] < mid:
  11.                     i += 1
  12.                     if arr[i] * y > arr[j] * x:
  13.                         x, y = arr[i], arr[j]
  14.                 count += i + 1
  15.             if count == k:
  16.                 return [x, y]
  17.             elif count > k:
  18.                 right = mid
  19.             elif count < k:
  20.                 left = mid

时间复杂度：O(n * logC)，空间复杂度：O(1)