Python编程之数据结构与算法练习_001

声明：题目出自《剑指Offer》。算法原理请自行找书撸， 不废话。直接上Python版本代码。

题目：求从小到大的顺序的第1500个丑数。我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）

1 1 #计算第1500个丑数
2 2 #1,2,3,4,5
3 3 import datetime
4 4 
5 5 startTime = datetime.datetime.now()
6 6 
7 7 uglyNumberList = [1]
8 8 indexList = [[0,2], [0,3], [0,5]]
9 9 
1010 while len(uglyNumberList) <= 1500:
1111     var = min(uglyNumberList[indexList[0][0]]*2, uglyNumberList[indexList[1][0]]*3, uglyNumberList[indexList[2][0]]*5)
1212     for i in range(0, 3):
1313         if uglyNumberList[indexList[i][0]]*indexList[i][1] == var:
1414             indexList[i][0] += 1
1515     else:
1616         uglyNumberList.append(var)
1717 else:   
1818     deltaTime = datetime.datetime.now() - startTime
1919     print("The 1500 ugly number is {}\nTime consuming is {} ms".format(uglyNumberList[-1], deltaTime.total_seconds()*1000))