丑数

python 算法

只包含素因子2、3和5的数称作丑数。1，2，3，4，5，6，8，9，10，12，15，16，18是最前面的13个丑数。但7 不是丑数，以 7 为素因子的数也不是丑数。

思路：
1. 首先 1 是丑数，创建一个仅含 1 的 list
2. 下一个丑数肯定是 list 中某几个数的 2 3 5 倍的最小值

# coding=utf-8
def ugly_number(index):
    if index < 1:
        return 0
    res = [1]
    t2 = t3 = t5 = 0
    next = 1
    while next < index:
        min_num = min(res[t2] * 2, res[t3] * 3, res[t5] * 5)
        res.append(min_num)
        if res[t2] * 2 <= min_num:
            t2 += 1
        if res[t3] * 3 <= min_num:
            t3 += 1
        if res[t5] * 5 <= min_num:
            t5 += 1
        next += 1
    return res[index-1]