推 digua: 大師 05/10 09:51
推 argorok: 大師 05/10 09:54
→ ILoveErr: 大師 05/10 09:57
推 DJYOSHITAKA: 大師 05/10 09:58
推 SecondRun: 好難 我吐了 05/10 10:00
推 JIWP: 別卷了 05/10 10:08
推 sustainer123: 大師 05/10 10:35
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