题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

时间限制：1秒；空间限制：32768K；本题知识点：数组

解题思路

用循环的思路很容易时间超出限制，可以这样考虑：根据丑数的性质，任意两个丑数相乘的结果还是丑数，任意大于1的丑数可以由一个丑数乘以2/3/5得到，如：

1*2=2，2*2=4，3*2=6，4*2=8……

1*3=3，2*3=6，3*3=9，4*3=12……

1*5=5，2*5=10，3*5=15，4*5=20……

可以分三组数据来考虑，并用三个索引值i1/i2/i3记录当前的丑数可由2/3/5哪个数计算出。每次循环只需要计算三次乘法的结果比较并记录最小值，然后更新索引值i，这样就能按从小到大的顺序得到丑数数组。

# -*- coding:utf-8 -*-class Solution:    def GetUglyNumber_Solution(self, index):        # write code here        if index==0:            return 0        l = [1] #丑数数组        i1,i2,i3 = 0,0,0 #索引值        while len(l)