刷 LeetCode 绕不开动态规划剑指 Offer 系列的这道丑数题绝对是我刷题路上印象很深的一道。题号是剑指 Offer 49LeetCode 上对应的还有 264. Ugly Number II本质是同一道题。很多第一次刷到的人会被“丑数”这个名字带偏以为是什么奇怪的数学难题其实拆开之后就是一个经典的“多路归并 动态规划”模型。这篇文章我会把它讲透从题目定义到三指针解法再到逐步手推最后把易错点和扩展题一起聊清楚适合刚入门动态规划、或者刷题时被这道题卡住的朋友。先放结论这道题最优解的时间复杂度是 O(n)空间复杂度也是 O(n)核心做法是三指针递推。你不需要理解什么高深数学只需要搞懂“丑数只能由丑数生成”这一句话。1. 题目拆解先搞懂“丑数”到底在问什么1.1 题目定义与关键条件先看题目本身的定义。所谓丑数是指只包含质因数 2、3 和 5 的正整数。这里注意几个细节1 是第一个丑数因为 1 没有质因数它的质因数集合是空集空集是“只包含 2、3、5”的所以 1 被约定为丑数。题目求的是“第 n 个丑数”比如 n 10 时前 10 个丑数是 1, 2, 3, 4, 5, 6, 8, 9, 10, 12所以答案是 12。约定 n 不超过 1690。这个上限不是随便给的因为第 1690 个丑数刚好在 int 范围内超出这个范围就可能有整数溢出风险。很多人会把这道题和另一道简单题“263. 丑数”搞混。263 是给你一个数判断它是不是丑数方法很简单让这个数循环除以 2、3、5最后看剩不剩 1。而剑指 Offer 49 是反向操作不给具体数字直接让你按顺序生成丑数序列难度完全不是一个量级。1.2 为什么暴力枚举走不通我第一反应很朴素既然要第 n 个丑数那就从 1 开始一个一个数对每个数都做因数分解判断它是否只包含 2、3、5直到数完 n 个为止。这个思路没毛病但效率太差了。假设第 n 个丑数是 X你要把 1 到 X 之间所有的整数都检查一遍其中绝大部分都不是丑数。丑数的分布并不是均匀的越往后越稀疏暴力检查的次数会远超 n。就算判断一个数是不是丑数只要 O(log n) 的时间总的复杂度也非常难看。LeetCode 上 n 最大到 1690暴力勉强能跑但如果扩展到超级丑数、或者 n 到 10 万级别暴力就彻底崩了。所以这道题真正的考点不是“判断丑数”而是“按顺序生成丑数”。顺着生成的方向想核心思路就浮出水面了。2. 动态规划三指针最优解的核心思路2.1 从“丑数生成丑数”的递推关系说起丑数有一个非常重要的性质一个丑数乘以 2、乘以 3、乘以 5得到的仍然是一个丑数。反过来想如果我们已经知道前 i-1 个丑数那么第 i 个丑数一定是由某个已经生成的丑数乘以 2、3 或 5 得来的。这个递推关系是做动态规划的基础。我可以用一个一句话版本描述丑数序列是一系列“由已有丑数乘以 2”“乘以 3”“乘以 5”得到的数合并排序后的结果。到这一步很多人会想到另一个方案维护一个最小堆每次弹出最小值然后把它的 2 倍、3 倍、5 倍都塞回去。这个方案可行后面第 5 节我会详细对比。但动态规划的思路更精妙它用三个指针替代了堆的排序操作把复杂度从 O(n log n) 降到了 O(n)。2.2 三指针的意义与指针移动规则既然我们要生成有序的丑数序列就可以把这个过程理解为三条“生产线”同时在跑生产线 A专门负责“某个丑数 × 2”得到 2, 4, 6, 8, 10, 12...生产线 B专门负责“某个丑数 × 3”得到 3, 6, 9, 12, 15...生产线 C专门负责“某个丑数 × 5”得到 5, 10, 15, 20...问题在于每条生产线产出的数字是递增的但三条线合并到一起后我们需要每次挑出最小的那个才能保证最终序列有序。这就需要一个类似“归并排序”的操作。动态规划用三个指针 p2、p3、p5 分别记录三条生产线“目前进行到哪一步”。初始时三个指针都指向第一个丑数 dp[1] 1。每一轮计算三个候选值next2 dp[p2] × 2next3 dp[p3] × 3next5 dp[p5] × 5取三者中的最小值作为下一个丑数 dp[i]。然后哪个候选值被选中对应的指针就向后移动一位。如果两个候选值相同比如 next2 和 next3 都等于 6那就两个指针一起移动保证不会把同一个丑数重复计入序列。你可能会问为什么最小的一定是下一个丑数因为 dp 数组已经有序dp[p2] 是“还没被乘 2 的丑数中最小的那个”所以 next2 是“还没出现的 ×2 结果中最小的”next3 和 next5 同理。三者取最小就是所有未出现的丑数中最小的一个。这个逻辑每一轮都成立所以生成的序列保证递增且不重不漏。2.3 完整代码实现先把最常用的 Python 写法放出来我用的是 dp 数组索引从 1 开始的版本逻辑最直观class Solution: def nthUglyNumber(self, n: int) - int: dp [0] * (n 1) dp[1] 1 p2 p3 p5 1 for i in range(2, n 1): num2, num3, num5 dp[p2] * 2, dp[p3] * 3, dp[p5] * 5 dp[i] min(num2, num3, num5) if dp[i] num2: p2 1 if dp[i] num3: p3 1 if dp[i] num5: p5 1 return dp[n]这段代码里最重要的细节是三个 if 是并列的不是 else if。一旦漏掉这个遇到重复值时就会把同一个丑数放进序列两次后面的结果就全错了。再看一个 C 版本思路完全一致class Solution { public: int nthUglyNumber(int n) { vectorint dp(n 1); dp[1] 1; int p2 1, p3 1, p5 1; for (int i 2; i n; i) { int num2 dp[p2] * 2; int num3 dp[p3] * 3; int num5 dp[p5] * 5; dp[i] min({num2, num3, num5}); if (dp[i] num2) p2; if (dp[i] num3) p3; if (dp[i] num5) p5; } return dp[n]; } };Java 版本同样不复杂顺手也放出来class Solution { public int nthUglyNumber(int n) { int[] dp new int[n 1]; dp[1] 1; int p2 1, p3 1, p5 1; for (int i 2; i n; i) { int num2 dp[p2] * 2; int num3 dp[p3] * 3; int num5 dp[p5] * 5; dp[i] Math.min(num2, Math.min(num3, num5)); if (dp[i] num2) p2; if (dp[i] num3) p3; if (dp[i] num5) p5; } return dp[n]; } }三种语言写法几乎一样核心逻辑就三件事取三个候选值、选最小、移动对应的指针。理解了这三件事代码闭着眼睛都能写出来。3. 图解模拟手推一遍 dp 数组的变化过程3.1 从 dp[1] 到 dp[5] 的第一轮推导光看代码还是有点抽象我建议你拿出一张纸跟着我一步步推。我们手动算前 5 个丑数把每一轮的指针状态都写下来。初始状态dp[1] 1p2 1p3 1p5 1。轮次候选 next2候选 next3候选 next5最小值dp[i]指针变化i21×221×331×552dp[2]2p2 从 1→2i32×241×331×553dp[3]3p3 从 1→2i42×242×361×554dp[4]4p2 从 2→3i53×262×361×555dp[5]5p5 从 1→2这个过程拆开看p2、p3、p5 就像三个“游标”各自指向一个丑数该轮到哪条生产线出数了对应游标就往前进一格。可以把这个过程理解成三路人马同时排着队每次从队首挑一个最小的数出来。3.2 从 dp[6] 到 dp[10]重复值怎么处理接下来是重点看重复值怎么出现、怎么处理。继续推第 6 到第 10 个丑数。此时 p2 3p3 2p5 2。轮次候选 next2候选 next3候选 next5最小值dp[i]指针变化i6dp[3]×26dp[2]×36dp[2]×5106dp[6]6p2 3→4p3 2→3i7dp[4]×28dp[3]×39dp[2]×5108dp[7]8p2 4→5i8dp[5]×210dp[3]×39dp[2]×5109dp[8]9p3 3→4i9dp[5]×210dp[4]×312dp[2]×51010dp[9]10p2 5→6p5 2→3i10dp[6]×212dp[4]×312dp[3]×51512dp[10]12p2 6→7p3 4→5注意第 6 轮next2 6next3 6两个候选相等。这说明 6 可以来自 3×2也可以来自 2×3这两条路都能到达同一个丑数。如果只移动一个指针另一个指针下次还会再算出 6序列里就会出现两个连续的 6这就是重复。所以遇到并列最小值时必须把所有等于最小值的候选对应指针全部后移一位这就是代码里同时用三个独立 if 判断的原因。第 9 轮同理next2 和 next5 都等于 10p2 和 p5 同时后移。这种“多个指针同时移动”的场景在 n 越大的时候越常见是这道题最容易写错的地方。3.3 图解结论把前 10 个丑数列出来1, 2, 3, 4, 5, 6, 8, 9, 10, 12。你可能会注意到 7 和 11 不在里面因为 7 和 11 都是质数它们既不是 2、3、5 的倍数也不是由 2、3、5 组合相乘得到的。这里也顺便验证了一个规律丑数序列并不是“所有 2、3、5 的倍数的简单混合”因为像 2×3×318、2×2×520 这些数也都会出现在后面的序列里。手推一遍之后dp 数组的递增性就非常直观了。每一轮加入的都是当前三个生产线里最小的“新产出”所以整体序列必然递增而指针后移保证了每个丑数只会被每条生产线“处理”一次不会产生遗漏。4. 常见问题与易错点排查4.1 高频问题速查表我把刷这道题时容易遇到的高频问题整理成一个速查表方便你对照排查问题原因解决方案输出结果少了某些丑数把 dp 数组初始值全设为 0导致 dp[p2] 之类的值取到 0dp[1] 必须初始化为 1其余位最后都会被覆盖序列中出现重复丑数用 else if 链接候选值判断用三个独立的 if保证重复最小值时所有对应指针都移动第 n 个丑数错误且整体偏大指针初始化错误比如 p2、p3、p5 从 0 开始但 dp[0] 没定义好明确索引语义要么统一从 1 开始要么统一从 0 开始数组越界没有把 dp 数组开成 n1 大小索引从 1 使用时数组长度必须为 n1面试时被问“为什么用 min 而不是 max”没理解序列递增性只有每次取最小值才能按顺序生成丑数4.2 刷题时容易踩的三个坑第一个坑是 dp 数组的索引语义混乱。有的题解用 dp[0] 表示第一个丑数三个指针初始化为 0有的用 dp[1] 表示第一个丑数指针初始化为 1。两种写法都对但如果你看题解时混着看很容易把自己绕晕。我的建议是固定使用 dp[1] 1 的版本逻辑更直观指针含义也更清楚。第二个坑是我前面反复强调的 else if。新手最容易在这个地方翻车因为大多数求最小值的场景都不需要考虑并列但丑数这道题里数列相乘产生的重叠非常频繁。2×3 和 3×2 结果相同2×5 和 5×2 结果也相同3×5 和 5×3 结果还是相同越往后重叠越多。如果你用 else if重复值就会被当作新增丑数放进去答案直接崩掉。第三个坑是面试时容易忽略“为什么这个解法是正确的”。很多人代码写出来了被面试官一问就卡壳。你要能说清楚两个点第一丑数乘 2、3、5 后仍是丑数所以生成规则成立第二每一轮取出的是三个候选里的最小值相当于三路归并保证了序列的单调性。这两句话能讲明白这道题才算真正会了。5. 解法对比与扩展思考5.1 最小堆解法理解容易但效率稍低除了动态规划三指针LeetCode 讨论区还有一种常见解法是用最小堆。思路是这样的初始时把 1 放入最小堆然后循环 n-1 次每次从堆顶弹出最小值 x再把 x×2、x×3、x×5 放入堆中不过放入前要用一个哈希集合去重因为同一个数可能由不同路径生成。循环结束后堆顶就是第 n 个丑数。最小堆解法的优点是思路非常朴素和“丑数只能由丑数生成”的定义直接对应几乎不用动脑子。但缺点也明显每次推入 3 个元素、弹出 1 个元素堆操作的时间复杂度是 O(log n)整体复杂度达到 O(n log n)。在 n 很小的时候两种解法看不出差别但面试官通常会追问“有没有更优的做法”这时候就需要回到三指针动态规划上来。另外堆解法还有一个空间上的劣势堆里最多会同时存在 O(n) 个候选值所以空间复杂度也是 O(n)和动态规划持平但常数更大。综合来看面试时优先展示动态规划解法是更稳的选择堆解法可以作为思路补充提一句。5.2 扩展从丑数到超级丑数这道题有个很自然的扩展题叫做“超级丑数”LeetCode 上对应第 313 题。它的定义几乎一样只是把固定的质因数集合从 {2, 3, 5} 换成一个长度可变的质数数组 primes。比如 primes [2, 7, 13, 19]让你求第 n 个超级丑数。做这道扩展题时三指针法就能直接迁移。你可以把原来的 p2、p3、p5 三个固定指针改成一个长度为 m 的指针数组 pointers其中 m 是 primes 的长度。每一轮遍历所有指针计算出 m 个候选值取最小值后把所有等于最小值的指针都后移一位。代码结构几乎不变但复杂度从 O(n×3) 变成 O(n×m)。这里有个非常实用的经验刷题时遇到“固定数量乘数”的题先想三指针动态规划遇到“数量不固定乘数”的变体就把三指针里的每一个“指针 乘数”对扩展成数组形式。掌握了这个套路你等于同时会做了两道题甚至可以说是一类题。再延伸一步这种“多路归并取最小”的思想在工程里也很常见。比如你有多个有序的数据源想合并成一个全局有序的流就可以用类似的指针思路如果数据源数量动态变化就改用优先队列来管理。剑指 Offer 49 表面上是一道算法题底层其实训练了最核心的“有序数组合并”思想这也是它为什么被经常拿来当面试题的原因。我个人在实际刷题时的体会是这道题第一次做很可能会卡在“为什么指针可以代表同一条生产线”这个理解上。你可以把它类比成三个人同时做菜一个人只做 2 的倍数一个人只做 3 的倍数一个人只做 5 的倍数每做完一道菜就继续做下一道。三人的出品速度不一样但每次只要从三份“最新成品”里挑一份最早上桌的就能保证所有菜按时间顺序上齐。想通了这一点三指针的代码就不再是死记硬背而是顺理成章的事了。最后再分享一个小技巧遇到动态规划的题如果递推关系里有“乘法因子”不妨先把因子单独拎出来当成几条独立序列画一画画完你往往就能找到和指针有关的解法这种思路在很多看似复杂的题里都挺管用。