264. 丑数 II

题目描述

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

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

思路

动态规划。因为丑数只是包含质因数 2、3 和/或 5 的正整数，因此我们可以使用三个指针从头遍历丑数数组。这三个指针分别是 2、3 和 5 的整数指针，记作 p2, p3, p5。每次计算第 n 个丑数时可以得出如下动归方程：

$$dp[n]=min(dp[p2]\ast 2,dp[p3]\ast 3,dp[p5]\ast 5)$$

之后比较 dp[n] 与这三个比较值，相等的话给对应指针加一，代表着已经越过了当前最小值，下一次比较的是稍大的值。

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [0 for i in range(n+1)]
        dp[1] = 1
        dp2 = dp3 = dp5 = 1
        for i in range(2, n + 1):
            n2, n3, n5 = dp[dp2]*2, dp[dp3]*3, dp[dp5]*5
            dp[i] = min(n2, n3, n5)
            if dp[i] == n2:
                dp2 += 1
            if dp[i] == n3:
                dp3 += 1
            if dp[i] == n5:
                dp5 += 1
        return dp[n]

想得太多