滄海一粟 第k小的分數(最小堆+生成應用) Leetcode #786

Aaron Burden on Unsplash

題目敘述

輸入給定一個已經從小到大排序好，而且彼此互質的整數陣列，
請問任取兩數分別當作分子、分母，第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 for i > 0.

第一個元素之外的都是質數。

• All the numbers of arr are 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)

Reference

[1] K-th Smallest Prime Fraction - LeetCode