LeetCode-264-丑数 II

编写一个程序，找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。

image.png

解题思路：

1. 三指针+动态规划；
2. 让我们从数组中只包含一个丑数数字1开始，使用三个指针i2, i3, i5标记所指向丑数要乘以的因子；
3. 在nums[i2]*2, nums[i3]*3, nums[i5]*5三个中，选出最小的丑数并添加到数组中。并将该丑数对应的因子指针往前走一步。重复该步骤直到计算完 n 个丑数。

Python3代码：

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