008: 寻找丑数

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

链接：https://leetcode.cn/problems/ugly-number-ii/description/

在构建列表的过程中，寻找丑数

输入：n = 1
输出：1
解释：1 通常被视为丑数。

方法1：

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = [1]
        index2 = 0
        index3 = 0
        index5 = 0
        for i in range(n-1):
            num = min(res[index2] * 2, res[index3] * 3, res[index5] * 5)
            res.append(num)
            if res[-1] == res[index2]*2:
                index2 += 1
            if res[-1] == res[index3]*3:
                index3 += 1
            if res[-1] == res[index5]*5:
                index5 += 1
        return res[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法2：

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        l = [1]
        p2 = 0
        p3 = 0
        p5 = 0
        while len(l) < n:
            m = min(l[p2]*2, l[p3]*3, l[p5]*5)
            l.append(m)
            if l[p2]*2 == m:
                p2 += 1
            if l[p3]*3 == m:
                p3 += 1
            if l[p5]*5 == m:
                p5 += 1
        return l.pop()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20