264. 丑数 II Python

---

一、题目描述

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

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

示例 1

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
1
2
3

示例 2

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

提示：1 <= n <= 1690

二、代码

代码如下：

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        result = [1]
        p2 = p3 = p5 = 0
        while len(result) < n:
            num = min(result[p2]*2,result[p3]*3,result[p5]*5)
            if num not in result:
                result.append(num)
            if result[p2]*2 == num:
                p2 += 1
            elif result[p3]*3 == num:
                p3 += 1
            else:
                p5 += 1
        print(result)
        print(result[n - 1])
        return result[n - 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

三、解题思路

本题考验对于“丑数”的定义及计算，丑数是只包含因子 2、3 和 5 的正整数，1为最小的丑数。本题要求找出指定位置的丑数是什么。关于丑数的计算主要需要考虑的是丑数的顺序，本题解的思路为每次为丑数序列中添加一个当前序列生成的丑数中的最小值，重复多次，直到丑数序列满足长度为n即可。丑数实际上可以通过正整数乘2或3或5生成，我们每次只需要判断当前序列中生成的最小丑数是谁即可，将其加入当前序列，重复以上过程。