0264：丑数 II（★）

2015-09-21 约 289 字预计阅读 1 分钟次阅读

力扣第 264 题

题目

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

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 1690

分析

#1

0263 升级版，可以用前面的丑数递推。

1
2
3
4
5
6
7


class Solution:
    def nthUglyNumber(self, n: int) -> int:
        P = [2,3,5]
        f = [1]*n
        for i in range(1,n):
            f[i] = min(f[j]*p for j in range(i) for p in P if f[j]*p>f[i-1])
        return f[-1]

9869 ms

#2

递推式中，对于质数 p，需要找到第一个 j 使得 f[j]*p>f[i-1]
显然 j 是随着 i 递增而递增的
因此考虑维护 p 对应的 j 即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def nthUglyNumber(self, n: int) -> int:
        P = [2,3,5]
        f = [1]*n
        g = defaultdict(int)
        for i in range(1,n):
            f[i] = min(f[g[p]]*p for p in P)
            for p in P:
                if f[g[p]]*p==f[i]:
                    g[p] += 1
        return f[-1]

199 ms

目录

0264：丑数 II（★）

题目

分析

#1

#2

解答