丑数

题目描述

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

思路

后面的丑数是由前面的丑数*2，*3，*5得到的，找到前面所有丑数*2，*3，*5，中最小的丑数即为下一个丑数，但是这样会有大量不必要的计算，因为前面所有丑数乘上2时，总有一部分小于当前最大的丑数，一部分大于当前最大的丑数，所以，想办法记录乘上2后大于当前数组最大值的最小值的索引处，3，5，同理。最终比较res[index2]*2,res[index3]*3,res[index5]*5)，选择最小的，放入结果中

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     def GetUglyNumber_Solution(self, index):
 4         # write code here
 5         if index <= 0:
 6             return 0
 7         res = []
 8         res.append(1)
 9         # 找在排序的数组中乘上2后大于当前数组最大值的最小值的索引处，3，5，同理
10         index2 = 0
11         index3 = 0
12         index5 = 0
13         for i in range(1,index,1):
14             while res[index2]*2<=res[-1]:
15                 index2 +=1
16             while res[index3]*3 <= res[-1]:
17                 index3 +=1
18             while res[index5] *5 <= res[-1]:
19                 index5 += 1
20             res.append(min(res[index2]*2,res[index3]*3,res[index5]*5))
21         return res[-1]