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

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

示例:

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

1 是丑数。
n 不超过1690。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ugly-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        record = [1 for _ in range(n)]
        i2, i3, i5 = 0, 0, 0
        for i in range(1, n):
            x = min(record[i2]*2, record[i3]*3, record[i5]*5)
            record[i] = x
            if record[i2]*2 == x:
                i2+=1
            if record[i3]*3 == x:
                i3+=1
            if record[i5]*5 == x:
                i5+=1
        return record[-1]