1.题目基本信息

1.1.题目描述

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是质因子只包含 2、3 和 5 的正整数。

1.2.题目地址

https://leetcode.cn/problems/ugly-number-ii/description/

2.解题方法

2.1.解题思路

动态规划（O(n)）

最小堆（O(nlogn)）

2.2.解题步骤

动态规划方法步骤：

• 第一步，状态定义。dp[i]表示第i个丑数

• 第二步，状态初始化。dp[1]=1

• 第三步，状态转移。dp[i]=min(dp[p2]2,dp[p3]3,dp[p5]5)。pj维护一个dp数组中指针，该指针保证dp[pj]j在下一轮丑数选择的候选者序列中；p2,p3,p5本质上是维护一个长度为3的候选丑数序列；所以在选择到最小dp[pj]*j后，都需要自增pj，将下一个质数j对应的候选丑数加到数组中

• 第四步，dp[n]即为题解

3.解题代码

python代码 - 动态规划

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        # 思路2：动态规划
        # 第一步，状态定义。dp[i]表示第i个丑数
        dp = [0] * (n + 1)
        # 第二步，状态初始化。dp[1]=1
        dp[1] = 1
        # 第三步，状态转移。dp[i]=min(dp[p2]*2,dp[p3]*3,dp[p5]*5)。pj维护一个dp数组中指针，该指针保证dp[pj]*j在下一轮丑数选择的候选者序列中；p2,p3,p5本质上是维护一个长度为3的候选丑数序列；所以在选择到最小dp[pj]*j后，都需要自增pj，将下一个质数j对应的候选丑数加到数组中
        p2 = p3 = p5 = 1
        for i in range(2, n + 1):
            num1, num2, num3 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
            dp[i] = min(num1, num2, num3)
            # 可能出现相同的元素，所以都使用if而不是elif
            if dp[i] == num1:
                p2 += 1
            if dp[i] == num2:
                p3 += 1
            if dp[i] == num3:
                p5 += 1
        # print(dp)
        # 第四步，dp[n]即为题解
        return dp[n]

python代码 - 最小堆

import heapq

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        # 思路1：最小堆+哈希表
        heap = [1]
        visited = set([1])
        for i in range(n - 1):
            x = heapq.heappop(heap)
            for num in [2, 3, 5]:
                val = x * num
                if val not in visited:
                    heapq.heappush(heap, val)
                    visited.add(val)
        return heapq.heappop(heap)

4.执行结果