N 的第 K 個因子 - O(sqrt n) 演算法

介紹

最近我寫了一篇文章《學習大O符號》一勞永逸。在那篇文章中，我回顧了 Big-O 備忘錄中提供的所有類型的 Big O 時間表示法。我認為除了這七個時間符號之外，不可能有更多的時間符號。

彷彿宇宙本身在羞辱我、嘲笑我的無知，我遇到了一道 LeetCode 問題，其解法需要 O(√n) 時間。 如果你瘋了，這可以翻譯成 O(N^1/2)。

問題

給你兩個正整數 n 和 k。整數 n 的因數被定義為整數 i，其中 n % i == 0。

考慮按升序排列的 n 的所有因子的列表，返回此列表中的第 k 個因子，如果 n 少於 k 個因子，則返回 -1。

顯而易見的解決方案

好吧，如果你像我一樣，你的第一個想法就是遍歷從 1 到 n 的每個數字，檢查它是否是一個因子，如果它在所需的 k 索引中，則返回它。

程式碼如下圖：

def getkthFactorOfN(n, k):
    result = 0
    for i in range(1, n + 1):
        if n % i == 0:
            result = result + 1
            if result == k:
                return i
    return -1

這一切都很好，但它是「僅」 O(n)。畢竟，只有一個循環，並且最多可達 n 1。
考慮時間符號時，所有其他操作都會被丟棄。

但是，我的朋友，有一個問題。

了解因素

如果你仔細想想，因素在某個點之後就會「鏡像」。

以數字 81 為例，它的因數為 [1, 3, 9, 27]，其中：

• 1 * 81 = 81
• 3 * 27 = 81
• 9 * 9 = 81
• 27 * 3 = 81
• 81 * 1 = 81

如果不算數字9，則操作只是重複和翻轉。如果將 n 除以它的一個因數，就會得到另一個因數。
期望 n 的平方根，即它本身的平方（廢話）。

有了這些知識，我們現在知道我們不需要迭代循環最多 n 次（範圍(1, n 1)），而只需迭代到 math.sqrt(n) 即可。之後，我們就得到了我們需要的所有因素！

不太明顯的解決方案

現在我們已經擁有了所需的一切，我們需要將這個循環從 1 -> 轉換為 1 -> 。 n 至 1 ->開方 n.

我只是將程式碼放在這裡，我們將逐行檢查這些行。

def getkthFactorOfN(n, k):
    i = 1
    factors_asc = []
    factors_desc = []
    while i * i <= n:
        if n % i == 0:
            factors_asc.append(i)
            if i != n // i:
                factors_desc.append(n // i)
        i += 1
    if k <= len(factors_asc):
        return factors_asc[k-1]
    k -= len(factors_asc)
    if k <= len(factors_desc):
        return factors_desc[-k]
    return -1

哦，這要複雜得多。讓我們來分解一下：

首先，我們初始化 i = 1。在搜尋因子時，該變數將用作「我們目前所在的數字」。

其次，我們將建立兩個陣列：factors_asc 和 Factors_desc。這裡的神奇之處在於，我們將向 Factors_asc 添加因子 - 它們如此命名是因為它們會自動按升序排列。
每當我們在factors_asc中添加一些內容時，我們都會將n除以它並將其添加到factors_desc。類似的邏輯在這裡；它們將按降序方便地添加。

然後，我們開始循環。在這裡，我將其更改為 while i * i

我們先檢查目前數字是否為因子 (n % i == 0)。如果是這樣，我們可以將其附加到我們的 Factors_asc 陣列中。

接下來，我們得到 i 的「逆因子」。我們可以透過檢查 i != n // i 是否，或者換句話說，它是否不是根來做到這一點。這是因為根不能在兩個數組中重複。如果不是，我們透過執行 n // i 並將結果附加到 Factors_desc 中來獲得反轉的因子。

之後，我們將 i 加 1 並繼續循環。

循環完成後，我們必須得到所需的所有階乘。

我們先透過 if k

如果不是，我們必須減去從 k 中找到的因子數量並再次檢查 - k -= len(factors_asc) 並且 k

如果 k 在 Factors_desc 內，則使用 Factors_desk[-k] 來取得其值（從最後到第一個）。

如果全部失敗，回傳-1。

曲線

如果你想知道它落在曲線圖中的哪個位置，它會在O(n) 和O(log n) 之間，比前者更好，也更差比後者。這是一個圖表：

Mathspace 提供

結論

這是一次發現和研究的旅程。非常感謝您閱讀到目前為止。

如果你想更優化，你可以建立factors_asc_len和factors_desc_len變量，並在每次向這些數組追加值時加1，這樣就不必調用方法len()，因為該方法是O(n) 因此它會影響時間符號。

祝你學習順利，下次再見！

以上是N 的第 K 個因子 - O(sqrt n) 演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！