记录一道ugly num的题目，该题给出一个数字n，需要程序给出第n个丑陋数，丑陋数的定义是数字拆解到最后，只能由2，3，5三个数字联乘，比如30 = 2 * 3 * 5就是丑陋数，而14 = 2 * 7由于7的存在，不是一个丑陋数，需要注意的是，1是一个特殊的丑陋数
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number, and n does not exceed 1690.
看到这道题，我首先想到的做法是遍历 + 动态规划的方法，用一个数组记录数是否为丑陋数，遍历判断当前数是否能够整除2，3，5，如果能，则当前数的丑陋性由相处之后的数决定，否则为非丑陋数，代码如下
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 6:
return n
flag = [True] * 7
i, cnt_ugly_num, res = 7, 6, None
while True:
if (i % 2 == 0 and flag[i / 2]) or \
(i % 3 == 0 and flag[i / 3]) or \
(i % 5 == 0 and flag[i / 5]):
flag.append(True)
cnt_ugly_num += 1
if cnt_ugly_num == n:
res = i
break
else:
flag.append(False)
i += 1
return res
这种思路超时了，分析了一下，应该是flag数组开的过大，于是思考了一下，能不能用数组只存丑陋数，当数组长度等于n了，就得到结果了，这种思路的问题在于如何顺序获得丑陋数，我们可以用三个idx来存储2，3，5三条线的下标，这样就能获得当前的最小值，代码如下
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
ugly_num = [1]
i2 = i3 = i5 = 0
while len(ugly_num) < n:
while ugly_num[i2] * 2 <= ugly_num[-1]: i2 += 1
while ugly_num[i3] * 3 <= ugly_num[-1]: i3 += 1
while ugly_num[i5] * 5 <= ugly_num[-1]: i5 += 1
ugly_num += min(ugly_num[i2] * 2, ugly_num[i3] * 3, ugly_num[i5] * 5),
return ugly_num[-1]
后来看discuss，发现还有一种效率最快的解决方法，直接得倒范围内所有的丑陋数，然后排序，得到第n个完事了，代码如下，这里解释一下，3 ** 20就大于2 ** 31了，5 ** 14同理
class Solution:
ugly = sorted(2**a * 3**b * 5**c
for a in range(32) for b in range(20) for c in range(14))
def nthUglyNumber(self, n):
return self.ugly[n-1]