$ cat ./coding/1492-the-kth-factor-of-n.md

────────────────────────────────────────────────────────────

1492. The kth Factor of n

這一個題目可以直接用暴力法來解，搜尋空間為 1 到 n/2 + 1，時間複雜度為 $\begin{array}{l}O(n/2)\\ approxO(n)\end{array}$ 。

class Solution:
    def kthFactor(self, n: int, k: int) -> int:
        for i in range(1, n//2+1):
            if n % i == 0:
                k -= 1
                if k == 0:
                    return i
        return n if k == 1 else -1

不過既然是第 k 個項目，多數只要是找第 k 個項目的題目，都可以試著用 heap 來想。

class Solution:
    def kthFactor(self, n: int, k: int) -> int:
        heap = []
        for x in range(1, int(n**0.5) + 1):
            if n % x == 0:
                heappush(heap, - x)
                if len(heap) > k:
                    heappop(heap)
                if x != n // x:
                    heappush(heap, - n // x)
                    if len(heap) > k:
                        heappop(heap)

        return -heappop(heap) if k == len(heap) else -1

$ ls ./coding/ | grep -v 1492-the-kth-factor-of-n