空间换时间。建立一个长度为n的数组,保存这n个丑数。在进行运算的时候,某个位置需要求得丑数一定是前面某个丑数乘以2、3或者5的结果,我们分别记录之前乘以2后能得到的最大丑数M2,乘以3后能得到的最大丑数M3,乘以5后能得到的最大丑数M5,那么下一个丑数一定是M2,M3,M5中的最小的那一个。同时注意到,已有的丑数是按顺序存放在数组中的。对乘以2而言,肯定存在某一个丑数T2,排在他之前的每一个丑数乘以2得到的结果都会小于已有的最大丑数,在他之后的每一个丑数乘以2得到的结果都会太大,我们只需记下这个丑数的位置,每次生成新的丑数的时候,去更新这个T2。对于3和5同理。

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

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        if index == None and len(index) <= 0:
            return 0

        uglyNumbers = [1]*index
        nextIndex = 1

        index2 = 0
        index3 = 0
        index5 = 0

        while nextIndex < index:
            minVal = min(uglyNumbers[index2]*2, uglyNumbers[index3]*3, uglyNumbers[index5]*5)
            uglyNumbers[nextIndex] = minVal

            while uglyNumbers[index2]*2 <= uglyNumbers[nextIndex]:
                index2 += 1
            while uglyNumbers[index3]*3 <= uglyNumbers[nextIndex]:
                index3 += 1
            while uglyNumbers[index5]*5 <= uglyNumbers[nextIndex]:
                index5 += 1
            nextIndex += 1

        return uglyNumbers[-1]


s = Solution()
print(s.GetUglyNumber_Solution(11))

# def getUglyNumber(index):
#     if index <= 0:
#         return 0
#
#     uglyNumbers = [1] * index
#     nextUglyIndex = 1
#
#     index2 = 0
#     index3 = 0
#     index5 = 0
#     multiply2 = uglyNumbers[index2]
#     multiply3 = uglyNumbers[index3]
#     multiply5 = uglyNumbers[index5]
#
#     while nextUglyIndex < index:
#         minVal = min(multiply2 * 2, multiply3 * 3, multiply5 * 5)
#         uglyNumbers[nextUglyIndex] = minVal
#
#         while multiply2 * 2 <= uglyNumbers[nextUglyIndex]:
#             index2 += 1
#             multiply2 = uglyNumbers[index2]
#         while multiply3 * 3 <= uglyNumbers[nextUglyIndex]:
#             index3 += 1
#             multiply3 = uglyNumbers[index3]
#         while multiply5 * 5 <= uglyNumbers[nextUglyIndex]:
#             index5 += 1
#             multiply5 = uglyNumbers[index5]
#
#         nextUglyIndex += 1
#     return uglyNumbers[-1]