题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
一开始最直观的的想法就是写出一个函数，输入数字能够判断是不是丑数。然后一直遍历所有的数字，一直到第N个丑数出现为止。
但是太耗时间。
解决办法：用空间换时间
因为太耗时间，于是我们想到用空间换时间的方式。我们发现，丑数可以由另外的丑数计算而来。比如，8由4乘以2得到。
因此
- 1、我们需要开辟空间，存储已有的丑数序列。
- 2、用已有的丑数序列，计算得到下一个丑数。
比如此时我们有丑数序列[1,2,3,4,5]，想要计算下一个丑数，那么我们就让已有的丑数序列每个数字都乘以2,3,5，得到三个序列，然后从这三个序列中，去掉已经存在的丑数，剩下的最小值，就是下一个丑数。
还能改进：
那么每次为了得到一个新的丑数，都需要用已有的丑数序列乘以2,3,5然后去重，筛选出最小的值吗？显然有很多是重复计算了的。
剑指offer的方法中指出，我们只需要找出特定的三个数字，然后用这三个数字分别乘以2,3,5得到三个数，选择其中最小值即可。
————————————————————————————————————
那么怎么确定这三个数呢？
因为上面已经说了，如果用所有的已有丑数乘以2,3,5会造成重复，那么从哪里开始，就不重复了呢？
比如上述的丑数序列中，乘以2为例，我们可以发现：
- 1,2,乘以2得到的值是重复的。
- 3乘以2等于6大于5。
- 4,5乘以2，都大于6了，肯定不会是下一个丑数了。
从上面我们能够发现，丑数数列乘以2为例，小于3的数字乘以2会重复，大于3的数字乘以2也没有什么用，那么就可以确定，只用一个数字3就能得到新的丑数的候选值。同样的，对于丑数数列乘以3，乘以5，会根据已有丑数2，2，得到丑数的候选值6,10.
很明显，我们会选候选值中最小的6作为新的丑数。
————————————————————————————————————
由上解释，可以知道改进方法，在乘以2时，用丑数中每个数乘以2，当得到的值刚大于序列中最大值M时，就把该值记作M2。同理，丑数序列中每个数乘以3，乘以5，得到M3，M5。然后选择其中最小的数作为新的丑数。就这样一直到第N个丑数。
综上，就是用一个长度为N的数列来存储N个丑数，达到以空间换时间的目的。
代码实现：
# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
if index == 0:
return 0
if index == 1:
return 1
#初始化丑数序列
res = [1]
for i in range(1,index):
#根据已有丑数序列，得到新的三个丑数候选值
M2_index = 0
M3_index = 0
M5_index = 0
while res[M2_index]*2 <= res[-1]:
M2_index += 1
M2 = res[M2_index]*2
while res[M3_index]*3 <= res[-1]:
M3_index += 1
M3 = res[M3_index]*3
while res[M5_index]*5 <= res[-1]:
M5_index += 1
M5 = res[M5_index]*5
#添加新的丑数
res.append(min(M2,M3,M5))
return res[-1]
S = Solution()
S.GetUglyNumber_Solution(6)
