目录

0264:丑数 II(★)

力扣第 264 题

题目

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

丑数 就是质因子只包含 235 的正整数。

示例 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