题目描述

[EN | CN]

编写一个程序,找出第 n 个丑数。

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

示例:

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

说明:

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

解法 1:动规

如果一个一个数算它是不是丑数,复杂度太高了。因此我们尝试基于已知的丑数来算接下来的丑数。

具体来说,我们可以设 3 个指针 i2i3i5 来分别表示接下来要乘以 2、3、5 的三个数的索引,然后每次要计算下一个丑数的时候,我们取这三个结果的最小值即可。

复杂度分析略。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        rets = [1]
        i2, i3, i5 = 0, 0, 0
        for _ in range(1, n):
            rets.append(min(rets[i2] * 2, rets[i3] * 3, rets[i5] * 5))
            if rets[-1] == rets[i2] * 2:
                i2 += 1
            if rets[-1] == rets[i3] * 3:
                i3 += 1
            if rets[-1] == rets[i5] * 5:
                i5 += 1
        return rets[-1]
  • 执行用时:192 ms,在所有 Python3 提交中击败了 60.69% 的用户。
  • 内存消耗:13.8 MB,在所有 Python3 提交中击败了 12.50% 的用户。