> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2021/12/jian-zhi-offer4900-zhong-deng-chou-shu.md).
# 丑数
 [](https://imhuay.gitbook.io/studies/algorithms/problems/2021/12/pages/R5NyOzkn3qAZy7wCx1pS#中等) [](https://imhuay.gitbook.io/studies/algorithms/problems/2021/12/pages/R5NyOzkn3qAZy7wCx1pS#剑指offer) [](https://imhuay.gitbook.io/studies/algorithms/problems/2021/12/pages/R5NyOzkn3qAZy7wCx1pS#动态规划) [](https://imhuay.gitbook.io/studies/algorithms/problems/2021/12/pages/R5NyOzkn3qAZy7wCx1pS#经典)
**问题简述**
```
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。
求按从小到大的顺序的第 n 个丑数。
```
详细描述
```
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/chou-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```
**思路：暴力解**
* 根据丑数的定义，有如下推论：
* 一个丑数乘以 2、3、5 之后，还是丑数；
* 从 1 开始，对每个丑数都乘以 2、3、5，再加入丑数序列（移除重复），那么不会产生遗漏；
* 对已有的丑数乘以 2、3、5，取其中大于已知最大丑数的最小值；
Python
```python
class Solution:
def nthUglyNumber(self, n: int) -> int:
dp = [1]
for i in range(1, n):
M = dp[-1] # 当前最大丑数
tmp = []
for x in dp[::-1]: # 逆序遍历
if x * 5 < M:
break
if x * 2 > M:
tmp.append(x * 2)
if x * 3 > M:
tmp.append(x * 3)
if x * 5 > M:
tmp.append(x * 5)
dp.append(min(tmp))
return dp[-1]
```
**思路：动态规划**
* 暴力解中存在大量重复计算，可以考虑动态规划；
Python
* 代码解读：[丑数，清晰的推导思路](https://leetcode-cn.com/problems/chou-shu-lcof/solution/chou-shu-ii-qing-xi-de-tui-dao-si-lu-by-mrsate/)
```python
class Solution:
def nthUglyNumber(self, n: int) -> int:
dp = [1] * n
p1, p2, p3 = 0, 0, 0 # 三指针归并
for i in range(1, n):
n2, n3, n5 = dp[p1] * 2, dp[p2] * 3, dp[p3] * 5
dp[i] = min(n2, n3, n5)
# 去重：使用 if 而不是 elif
if dp[i] == n2:
p1 += 1
if dp[i] == n3:
p2 += 1
if dp[i] == n5:
p3 += 1
return dp[-1]
```
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://imhuay.gitbook.io/studies/algorithms/problems/2021/12/jian-zhi-offer4900-zhong-deng-chou-shu.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.