描述
设计一个算法，找出只含素因子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。

代码
import heapq

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