丑数

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

思路：我们可以维护三个list，分别是乘2得到的丑数，乘3得到的丑数，乘5得到的丑数，但这样复杂度较高，而且会得到重复的丑数。实际上每次我们只用比较3个数：用于乘2的最小的数、用于乘3的最小的数，用于乘5的最小的数。这样只需要维护三个指针，而不用维护三个数组。

def GetUglyNumber_Solution(self, index):
    # write code here
    if index <= 0:
        return 0
    uglyList = [1]
    p2 = 0 # p2指向小于newUgly且最大的乘以2后可能成为下一个丑数的丑数
    p3 = 0 # p3指向小于newUgly且最大的乘以3后可能成为下一个丑数的丑数
    p5 = 0 # p5指向小于newUgly且最大的乘以5后可能成为下一个丑数的丑数
    for i in range(index-1):
        newUgly = min(uglyList[p2]*2, uglyList[p3]*3, uglyList[p5]*5)
        uglyList.append(newUgly)
        if (newUgly % 2 == 0):
            p2 += 1
        if (newUgly % 3 == 0):
            p3 += 1
        if (newUgly % 5 == 0):
            p5 += 1
    return uglyList[-1]