Re: [閒聊] 每日leetcode已回收
https://leetcode.com/problems/k-th-smallest-prime-fraction/description
786. K-th Smallest Prime Fraction
給你一個遞增的質數不重複數字陣列，第一個數字是1，求出不重複質數可組成的第k
小分數。
思路：
1.求第k小的數字，會先想到heap，最小分數一定是分子為1的，所以我們把除了arr[0]以
外的分母都配1丟進heap。
2.從heap pop k次，每次都讓分子變大並重新入隊，因為陣列排序好了所以一直讓索引變
大就好。
py code
-----------------------------------
class Solution:
def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
min_heap = []
n = len(arr)
for i in range(1, n):
heapq.heappush(min_heap, (1/arr[i], 0, i))
while True:
f, i, j = heapq.heappop(min_heap)
k -= 1
if k == 0:
return [arr[i], arr[j]]
if i + 1 < n:
heapq.heappush(min_heap, (arr[i + 1]/arr[j], i + 1, j))
-----------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.139.223.76 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715305738.A.A04.html
推
05/10 09:51,
1年前
, 1F
05/10 09:51, 1F
推
05/10 09:54,
1年前
, 2F
05/10 09:54, 2F
→
05/10 09:57,
1年前
, 3F
05/10 09:57, 3F
推
05/10 09:58,
1年前
, 4F
05/10 09:58, 4F
推
05/10 10:00,
1年前
, 5F
05/10 10:00, 5F
推
05/10 10:08,
1年前
, 6F
05/10 10:08, 6F
推
05/10 10:35,
1年前
, 7F
05/10 10:35, 7F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 204 之 1552 篇)：