面试题49. 丑数.md

题目：

编写一个程序，找出第 n 个丑数。

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

示例:

输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 说明:  

1 是丑数。 n 不超过1690。

解析1：

动态规划。

算法流程： 重点是DP的状态转移方程：dp[i] = min(2*dp[p2], 3*dp[p3], 5*dp[p5]) p2,p3,p5分别是三个指针，代表最靠前，最新的没有被乘以2，3，5的数值的指针。这里有点拗口。我们一次求丑数的时候，新的丑数肯定是以前的某个数或者某几个数乘以2，3，5得到的。如果最后一个数，大于前面的数乘以2，3，5，那么将对应的指针加1。因为n很小，所以复杂度可以认为是O(1)。

三个指针代表什么呢，代表，当前指针后面的数都不是当前值乘以2/3/5得到的。比如p2，代表已知p2后面的数，都不是p2值乘以2得到的。

复杂度：

	复杂度	大小	百分比
时间	$O(1)$	240 ms	43.20%
空间	$O(n)$	13.7 MB	6.09%

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