LeetcodeMedium-【面试题49. 丑数】*

我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

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

注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/

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

思路1：动态规划

题解

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        nums = [1] * n
        index1 = 0
        index2 = 0
        index3 = 0
        for i in range(1, n):
            nums[i] = min(nums[index1]*2, min(nums[index2]*3, nums[index3]*5))
            # 必须分开判断，不能用分支，因为上面的可能有相等的情况，相等的都要加+1,例如：2*3和3*2
            if nums[i] == nums[index1] * 2:
                index1 += 1
            if nums[i] == nums[index2] * 3:
                index2 += 1
            if nums[i] == nums[index3] * 5:
                index3 += 1
        # print(nums)
        return nums[n-1]