leetcode [面试题49] 丑数

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:  

    1 是丑数。
    n 不超过1690。

来自题解:

从1开始，增加一个当前值乘2，3，5中最小的，如果乘的是几，那么该索引增加1。

class Solution(object):
    def nthUglyNumber(self, index):
        """
        :type n: int
        :rtype: int
        """
        if index <= 1: return index
        res = [1] * index
        i2, i3, i5 = 0, 0, 0
        for i in range(1, index):
            res[i] = min(res[i2] * 2, res[i3] * 3, res[i5] * 5)
            if res[i] == res[i2] * 2: i2 += 1
            if res[i] == res[i3] * 3: i3 += 1
            if res[i] == res[i5] * 5: i5 += 1
        return res[-1]