寻找第n个丑数
应用案例
编写一个程序，找出第n个丑数。
案例分析
丑数的概念
一个数的因子仅仅包括2，3，5的数称为丑数。
说明1：数字1特别对待也看作是丑数。
说明2：从1开始的10个丑数分别为1，2。3。4，5，6，8，9。10。12。
过程分析
该题理解的关键之处在于：从丑数分解出来的因子，一定是一个丑数，即丑数一定是由丑数相乘得到的。所以，丑数的2，3，5倍均是一个丑数。
所以该题的核心为：默认第一个丑数是1，用第一个丑数 1 做 1×2；1×3；1×5；从这三个数字中选择一个最小的即为第二个丑数，结果是2；然后分别求第一个丑数和第二个丑数的2/3/5倍（除去已有的丑数2），取最小的作为第三个丑数；以此类推，求每个丑数的2/3/5倍，并作比较取最小的。
具体分析过程如下图：
代码实现
def getUglyNum(index):
if index < 1:
return 0
#默认第一个丑数
res = [1]
#t2、t3、t5是丑数列表res的下标
t2 = t3 = t5 = 0
nextdex = 1
while nextdex < index:
minNum = min(res[t2] * 2, res[t3] * 3, res[t5] * 5)
res.append(minNum)
#注意：这里是使用三个while循环，而不用if...else...
#当上述执行到第5步时，存在两个元素的结果相同的情况
while res[t2] * 2 <= minNum:
t2 += 1
while res[t3] * 3 <= minNum:
t3 += 1
while res[t5] * 5 <= minNum:
t5 += 1
nextdex += 1
return res[nextdex-1]
print(getUglyNum(10))执行结果如下所示：
12