题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
思路
思路1.暴力法
需要遍历所有数，o(n^2)复杂度，超时。
思路2.暴力+存储
也需要遍历所有数，只是反证丑数时节约时间，o(n^2)复杂度，依旧超时。
思路3.存储最小丑数，依次向上取，o(n)复杂度。
#思路1、2
# 1 2 3 4 5 6 8
# def is_ugly(n):
# while n % 2 == 0:
# n /= 2
# while n % 3 == 0:
# n /= 3
# while n % 5 == 0:
# n /= 5
# return n == 1
def GetUglyNumber_Solution(index):
# write code here
if index <= 0: return 0
if index == 1: return 1
uglys = {1}
cnt = 0
i = 0
while cnt < index-1:
i += 1
if i/2.0 in uglys or i/3.0 in uglys or i/5.0 in uglys:
cnt += 1
uglys.add(i)
return i
print(GetUglyNumber_Solution(700))#思路2：
def GetUglyNumber_Solution(index):
# write code here
if index <= 1: return index
res = [1] * index
i2, i3, i5 = 0, 0, 0
for i in range(1, index):
res[i] = min(res[i2]*2, min(res[i3]*3, res[i5]*5))
if res[i] == res[i2]*2: i2 += 1
if res[i] == res[i3]*3: i3 += 1
if res[i] == res[i5]*5: i5 += 1
return res[-1]
print(GetUglyNumber_Solution(700))