[leetcode/lintcode 題解] 阿裡算法面試真題：醜數 II · Ugly Number II

描述

設計一個算法，找出隻含素因子2，3，5 的第 n 小的數。

符合條件的數如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...：

我們可以認為 1 也是一個醜數。

線上評測位址：

領扣題庫官網

樣例1
輸入：9
輸出：10           

樣例2
輸入：1
輸出：1           

解題思路1：最小堆

• 很容易想到的方法是：從1起檢驗每個數是否為醜數，直到找到n個醜數為止。但是随着n的增大，絕大部分數字都不是醜數，我們枚舉的效率非常低。是以，換個角度思考，如果我們隻生成醜數，且生成n個，這道題就迎刃而解。
• 不難發現生成醜數的規律：如果已知醜數ugly，那麼ugly 2，ugly 3和ugly * 5也都是醜數。
• 既然求第n小的醜數，可以采用最小堆來解決。每次彈出堆中最小的醜數，然後檢查它分别乘以2、3和 5後的數是否生成過，如果是第一次生成，那麼就放入堆中。第n個彈出的數即為第n小的醜數。

算法流程

• 建立最小堆heap，哈希表 seen和質因數清單factors = [2, 3, 5]。heap用于存儲已生成的醜數，彈出最小值；seen用于标記堆中出現過的元素，避免重複入堆。
• 初始化将1入堆，并添加到seen。
• 重複以下步驟n次： 彈出堆中最小的數字 curr_ugly。 對于factors中每個因數f，生成新的醜數new_ugly。若new_ugly不在seen中，則将其添加到heap中并更新seen。
• curr_ugly即為第n小的醜數，傳回。

複雜度分析

• 時間複雜度：O(nlog(n))O(nlog(n))。彈出每個最小值時，時間複雜度都為堆的高度，是以時間複雜度為O(nlog(n))O(nlog(n))。
• 空間複雜度：O(n)O(n)。周遊n個醜數，并将每個醜數乘以2、3和5的結果存入堆中。堆和哈希表的元素個數都不會超過n * 3。

代碼

import heapq

class Solution:
    """
    @param n: An integer
    @return: return a  integer as description.
    """
    def nthUglyNumber(self, n):
        heap = []
        heapq.heappush(heap, 1)

        seen = set()
        seen.add(1)

        factors = [2, 3, 5]

        curr_ugly = 1
        
        for _ in range(n):
            # 每次彈出目前最小醜數
            curr_ugly = heapq.heappop(heap)
            # 生成新的醜數
            for f in factors:
                new_ugly = curr_ugly * f
                if new_ugly not in seen:
                    seen.add(new_ugly)
                    heapq.heappush(heap, new_ugly)
        return curr_ugly           

解題思路2：動态規劃

• 在最小堆方法中，我們的思路是把目前醜數能生成的醜數都加入到堆中，然後再彈出最小值。如果我們能知道下一個最小的醜數，每次隻生成最小的那個，就可以節省最小值查詢的時間消耗。
• 采用動态規劃的方法，用一個有序數組dp記錄前n個醜數。三個指針l2，l3和l5指向dp中的元素，最小的醜數隻可能出現在dp[l2]的2倍、dp[l3]的3倍和dp[l5]的5倍三者中間。通過移動三個指針，就能保證生成的醜數是有序的。

• 初始化數組dp和三個指針l2、l3和l5。dp[0] = 1，表示最小的醜數為1。三個指針都指向dp[0]。
• 重複以下步驟n次，dp[i]表示第i + 1小的醜數：
  • 比較2 dp[l2], 3 dp[l3], 5 * dp[l5]三者大小，令dp[i]為其中的最小值。
  • 如果dp[i] == 2 * dp[l2]，l2指針後移一位。
  • 如果dp[i] == 3 * dp[l3]，l3指針後移一位。
  • 如果dp[i] == 2 * dp[l5]，l5指針後移一位。
• dp[n - 1]即為第n小的醜數，傳回。

• 時間複雜度：O(n)O(n)。生成一個醜數隻需常量時間，是以生成n個醜數需要O(n)O(n)。
• 空間複雜度：O(n)O(n)。dp數組的長度為n。

class Solution:
    """
    @param n: An integer
    @return: return a  integer as description.
    """
    def nthUglyNumber(self, n):
        dp = [0] * n
        dp[0] = 1
        l2, l3, l5 = 0, 0, 0
        for i in range(1, n):
            # 生成第i+1小的醜數
            dp[i] = min(2 * dp[l2], 3 * dp[l3], 5 * dp[l5])
            if dp[i] == 2 * dp[l2]:
                l2 += 1
            if dp[i] == 3 * dp[l3]:
                l3 += 1
            if dp[i] == 5 * dp[l5]:
                l5 += 1
        return dp[n - 1]           

更多題解參考：

九章官網solution