面试题49：丑数

题目描述：

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

解题思路：

思路一：逐个判断每一整数是不是丑数，其中判断一个丑数可以通过以下代码：

while number%2==0:
    number = number/2
while number%3 == 0:
   number = number/3
while number%5 ==0:
   number = number/5
if number ==1:
   return True
else:
   return False

该方法时间效率不高，需要计算很多非丑数的判断。

思路二：
T2：表示排在他之前的每个丑数2得到的结果都会小于已有最大的丑数；在它之后的每个丑数2得到的结果都会太大。
T3,T5同理表示。

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index<=0:
            return 0
        uglynumbers = [1]
        ugly2 = 0
        ugly3 = 0
        ugly5 = 0
        index -= 1
        while index:
            #计算M2,M3,M5中最小的数做为下一个丑数
            min_ugly = min(uglynumbers[ugly2]*2,uglynumbers[ugly3]*3,uglynumbers[ugly5]*5)
            uglynumbers.append(min_ugly)
            #更新T2,T3,T5
            while uglynumbers[ugly2]*2<=uglynumbers[-1]:
                ugly2 += 1
            while uglynumbers[ugly3]*3 <= uglynumbers[-1]:
                ugly3 += 1
            while uglynumbers[ugly5]*5 <= uglynumbers[-1]:
                ugly5 += 1
            index -= 1
        return uglynumbers[-1]