剑指 Offer 49. 丑数 #

标签：哈希表、数学、动态规划、堆（优先队列）
难度：中等

题目大意 #

给定一个整数 n。

要求：找出并返回第 n 个丑数。

丑数：只包含质因数 2、3、5 的正整数。

解题思路 #

动态规划求解。

定义状态 dp[i] 表示第 i 个丑数。

状态转移方程为：dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5) ，其中 p2、p3、p5 分别表示当前 i 中 2、3、5 的质因子数量。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [1 for _ in range(n)]
        p2, p3, p5 = 0, 0, 0
        for i in range(1, n):
            dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)
            if dp[i] == dp[p2] * 2:
                p2 += 1
            if dp[i] == dp[p3] * 3:
                p3 += 1
            if dp[i] == dp[p5] * 5:
                p5 += 1
        return dp[n - 1]