题解 | #丑数#

题目：https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param index int整型 
# @return int整型
#
class Solution:
    def GetUglyNumber_Solution(self , index: int) -> int:
        if index==0:
            return 0
        i2=i3=i5=0
        res=[1]# 第一个丑数为 1
        for i in range(1,index):
            ugly=min(2*res[i2],3*res[i3],5*res[i5])
            res.append(ugly)
            if ugly==res[i2]*2:
                i2=i2+1
            if ugly==res[i3]*3:#注意不是写elif。举例数字6，对于i2和i3都要++
                i3=i3+1
            if ugly==res[i5]*5:
                i5=i5+1
        return res[-1]
#要点：
#（1）从1开始判断每个数是不是丑数，直到枚举到第n个，是一种思路。（判断的思路）
#另一种思路是找到丑数的规律，生成丑数。（生成的思路）
#（2）生成思路：后面的丑数都是前面的丑数生成的。前面生成的每个数都乘以2,3,5，
#然后检查出里面跟前面n-1个丑数不重复的并且是最小的数。