Article / 文章
LeetCode 第264题：丑数 II
编写一个程序，找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。
📖 文章摘要
本文详细解析LeetCode第264题“丑数 II”，这是一道动态规划问题。文章提供了从暴力解法到动态规划的完整思路演进，包含C#、Python、C++三种语言实现，配有详细的三指针技术图解和性能分析。适合想要深入理解动态规划和指针技巧的算法学习者。
核心知识点： 动态规划、三指针技术、数学运算、优化算法
难度等级： 中等
推荐人群： 动态规划学习者、算法优化爱好者
题目描述
编写一个程序，找出第 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
解题思路
丑数是质因数只包含 2、3、5 的正整数。按照定义，1 也是丑数。我们需要找出第 n 个丑数。
方法一：暴力解法（不推荐）
最直接的方法是从 1 开始，依次判断每个数是否为丑数，直到找到第 n 个丑数。但这种方法效率很低，因为丑数在自然数中的分布是稀疏的，大部分数都不是丑数。
方法二：动态规划（推荐）
我们可以通过已知的丑数来生成新的丑数。具体来说，如果 x 是丑数，那么 2x, 3x, 5x 也都是丑数。
核心思想：
- 初始时，只有一个丑数 1
- 定义三个指针
p2,p3,p5，初始都指向第一个丑数（即值为 0 的下标） - 在每一步中，我们选择
min(2*dp[p2], 3*dp[p3], 5*dp[p5])作为下一个丑数 - 然后将对应的指针向后移动一位
- 重复步骤 3 和 4，直到生成第 n 个丑数
这种方法实际上是通过三个队列合并的思想，每个队列分别是之前的丑数乘以 2、3、5 的结果。
复杂度分析：
- 时间复杂度：O(n)，我们需要计算前 n 个丑数
- 空间复杂度：O(n)，用于存储前 n 个丑数的数组
图解思路
动态规划状态转移表
| 步骤 | p2指向 | p3指向 | p5指向 | 候选值 | 下一个丑数 | 指针更新 |
|---|---|---|---|---|---|---|
| 初始 | 0(1) | 0(1) | 0(1) | - | dp[0]=1 | - |
| 1 | 0(1) | 0(1) | 0(1) | 2,3,5 | dp[1]=2 | p2++ |
| 2 | 1(2) | 0(1) | 0(1) | 4,3,5 | dp[2]=3 | p3++ |
| 3 | 1(2) | 1(2) | 0(1) | 4,6,5 | dp[3]=4 | p2++ |
| 4 | 2(3) | 1(2) | 0(1) | 6,6,5 | dp[4]=5 | p5++ |
| 5 | 2(3) | 1(2) | 1(2) | 6,6,10 | dp[5]=6 | p2++,p3++ |
三指针追踪过程表
| 丑数序列 | p2候选 | p3候选 | p5候选 | 最小值 | 说明 |
|---|---|---|---|---|---|
| [1] | 2×1=2 | 3×1=3 | 5×1=5 | 2 | 选择2，p2前进 |
| [1,2] | 2×2=4 | 3×1=3 | 5×1=5 | 3 | 选择3，p3前进 |
| [1,2,3] | 2×2=4 | 3×2=6 | 5×1=5 | 4 | 选择4，p2前进 |
| [1,2,3,4] | 2×3=6 | 3×2=6 | 5×1=5 | 5 | 选择5，p5前进 |
| [1,2,3,4,5] | 2×3=6 | 3×2=6 | 5×2=10 | 6 | 选择6，p2和p3都前进 |
代码实现
C# 实现
public class Solution {
public int NthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; i++) {
int next2 = dp[p2] * 2;
int next3 = dp[p3] * 3;
int next5 = dp[p5] * 5;
int nextUgly = Math.Min(Math.Min(next2, next3), next5);
dp[i] = nextUgly;
// 注意这里不是if-else结构，因为可能存在重复值
if (nextUgly == next2) p2++;
if (nextUgly == next3) p3++;
if (nextUgly == next5) p5++;
}
return dp[n - 1];
}
}Python 实现
class Solution:
def nthUglyNumber(self, n: int) -> int:
dp = [0] * n
dp[0] = 1
p2 = p3 = p5 = 0
for i in range(1, n):
next2 = dp[p2] * 2
next3 = dp[p3] * 3
next5 = dp[p5] * 5
dp[i] = min(next2, next3, next5)
# 注意这里不是if-elif结构，因为可能存在重复值
if dp[i] == next2:
p2 += 1
if dp[i] == next3:
p3 += 1
if dp[i] == next5:
p5 += 1
return dp[n - 1]C++ 实现
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n);
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; i++) {
int next2 = dp[p2] * 2;
int next3 = dp[p3] * 3;
int next5 = dp[p5] * 5;
dp[i] = min(next2, min(next3, next5));
// 注意这里不是if-else结构，因为可能存在重复值
if (dp[i] == next2) p2++;
if (dp[i] == next3) p3++;
if (dp[i] == next5) p5++;
}
return dp[n - 1];
}
};执行结果
C# 实现
- 执行用时：40 ms
- 内存消耗：29.2 MB
Python 实现
- 执行用时：96 ms
- 内存消耗：15.8 MB
C++ 实现
- 执行用时：4 ms
- 内存消耗：7.6 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C++ | 4 ms | 7.6 MB | 性能最佳，内存占用较小 |
| C# | 40 ms | 29.2 MB | 性能中等，内存占用较大 |
| Python | 96 ms | 15.8 MB | 代码简洁，但执行较慢 |
代码亮点
- 🎯 使用三指针技术，分别指向当前可能的下一个丑数的候选者
- 💡 采用动态规划思想，利用已知丑数生成新丑数，避免重复计算
- 🔍 通过取最小值确保丑数按照顺序生成，保证结果正确性
- 🎨 巧妙处理重复值的情况，确保不会漏掉任何丑数
常见错误分析
- 🚫 使用if-else结构而不是多个if判断，会导致某些丑数被跳过
- 🚫 忘记处理重复值情况，导致生成的丑数序列不连续
- 🚫 使用暴力解法检查每个数，效率极低，无法通过大数据测试
- 🚫 使用优先队列或有序集合实现时未处理重复元素
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 暴力法 | O(m*log m) | O(1) | 实现简单 | 效率极低，m为第n个丑数的值 |
| 动态规划 | O(n) | O(n) | 高效直观，线性时间复杂度 | 需要额外空间存储中间结果 |
| 优先队列/最小堆 | O(n log n) | O(n) | 思路清晰 | 需要处理重复元素，复杂度较高 |
相关题目
- LeetCode 263. 丑数 - 简单
- LeetCode 313. 超级丑数 - 中等
- LeetCode 1201. 丑数 III - 中等
- LeetCode 204. 计数质数 - 简单
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第264题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！