剑指Offer49-丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
-
1 是丑数。
-
n 不超过1690。
来源：力扣（LeetCode）
链接：力扣
一解
根据定义，丑数为 2^x * 3^y * 5^z ，其中 x, y, z 属于 n（0, 1, 2,…），只要根据上述公式依次进行计算即可。
设数组 a 存储丑数，从第一轮计算中最小值 p1, p2, p3 都是 1 ，加入 a ：
class Solution:
def nthUglyNumber(self, n: int) -> int:
p2, p3, p5 = 0, 0, 0
a = [1]
for i in range(2, n+1):
new_num = min(a[p2] * 2, a[p3] * 3, a[p5] * 5)
a.append(new_num)
if new_num == a[p2] * 2: p2 += 1
if new_num == a[p3] * 3: p3 += 1
if new_num == a[p5] * 5: p5 += 1
return a[-1]