264. Ugly Number II

编写程序寻找第n个“丑陋数” ugly number

丑陋数是指只包含质因子2, 3, 5的正整数。例如，1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前10个丑陋数。

注意，数字1也被视为丑陋数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 6 star, 很巧妙的解法，多练几遍
        a, b, c = 0, 0, 0
        result = [1 for _ in range(n)]
        for i in range(1, n):
            result[i] = min(result[a]*2, result[b]*3, result[c]*5)
            if result[i] == result[a]*2:
                a += 1
            if result[i] == result[b]*3:
                b += 1
            if result[i] == result[c] * 5:
                c += 1
        return result[n-1]