題目敘述
輸入給定一個已經從小到大排序好，而且彼此互質的整數陣列，
請問任取兩數分別當作分子、分母，第k小的分數是多少?
輸出請以[分子，分母]的形式回傳答案。
原本的英文題目敘述
測試範例
Example 1:
Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.
Example 2:
I
nput: arr = [1,7], k = 1
Output: [1,7]
約束條件
Constraints:
2 <= arr.length <= 1000
陣列長度介於2~1000之間。
1 <= arr[i] <= 3 * 10^4
每個元素介於1~三萬之間。
arr[0] == 1
第一個元素保證是1
arr[i]is a prime number fori > 0.
第一個元素之外的都是質數。
- All the numbers of
arrare unique and sorted in strictly increasing order.
數字彼此都不同，而且嚴格遞增排序。
1 <= k <= arr.length * (arr.length - 1) / 2
k 落在 C(n,2) 以內的數字。
演算法 最小堆 + 最佳化生成
比較小的分數一定是真分數，真分數就是分子比分母小。
例如:
1/2, 1/3, 1/5, 2/3, 2/5 ...等等
因此可以過濾掉另一半假分數的情況。
例如:
2/1, 3/1, 5/1, 3/2, 5/2 ...等等
一開始先建立一個空的最小堆，接著初始化成1/a, a是所有題目供應互質的整數。
問第k小，所以就是pop次，每次pop的時候，動態生成下一個最接近的分數往上成長。
第k次pop拿到的，恰好就是第k小的分數。
說明:
第一次pop拿到的會是第一小的分數，
第二次pop拿到的會是第二小的分數，
...
第k次pop拿到的的會是第k小的分數。
這是來自於minHeap最小堆的特性，pop的元素具有由小到大遞增的性質。
程式碼 最小堆 + 最佳化生成
class Solution:
def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
minHeap = []
# Initialize to 1/a, where a is integer in input array
for i in range(len(arr)):
heapq.heappush(minHeap,(1/arr[i], 0, i) )
# Pop k times, then latest item is the k-th smallest fraction
for _ in range(k):
fraction, numerator, denominator = heapq.heappop( minHeap )
if numerator + 1 < denominator:
# Grow to next closet fraction
heapq.heappush(minHeap, ( (arr[numerator+1])/arr[denominator], numerator+1, denominator) )
# k-th smallest fraction
return [ arr[numerator], arr[denominator] ]
複雜度分析
時間複雜度: O(k log n)
k次pop，每次動態生成對應的adjustment需要log(n)的時間成本。
空間複雜度: O(n)
初始化之後，minHeap堆積大小為O(n)。
每次迭代最多一進一出，minHeap堆積大小空間成本為O(n)
關鍵知識點
找前k大的元素，可以用最大堆maxHeap來滿足，
同樣道理
找前k小的元素，可以用最小堆minHeap來滿足。
當k比較小的時候，堆積演算法會比sorting來的有效率，
因為sorting至少要花費O( n lo n)
