剑指 Offer 49. 丑数

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

示例:

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

• 1 是丑数。
• n 不超过1690。

Python 解答：
1.暴力超时

class Solution:
    def nthUglyNumber(self, n: int) -> int:

        def isUgly(num):
            while num % 2 == 0:
                num //= 2
            while num % 3 == 0:
                num //= 3
            while num % 5 == 0:
                num //= 5
            if num == 1:
                return True
            else:
                return False
        i = 1
        count = 0
        while True:
            if isUgly(i):
                count += 1
            if n == count:
                return i
            i += 1

2.合并排序

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        alist = [1]
        i, j, k = 0, 0, 0
        while len(alist) < n:
            two = alist[i]*2
            three = alist[j]*3
            five = alist[k]*5
            temp = min(two, three, five)
            if temp == two:
                i += 1
            if temp == three:
                j += 1
            if temp == five:
                k += 1
            alist.append(temp)
        return alist[n-1]