1. 先看题丑数到底在考什么这道题我第一次看到的时候第一反应是丑数丑什么丑这名字起得也太随意了。但实际上丑数在算法面试里的出场率一点都不低尤其是剑指 Offer 系列它几乎是动态规划入门阶段非常经典的一道题。先说定义丑数就是只包含质因子 2、3 和 5 的正整数。注意是只包含。1 通常被视为第一个丑数因为它的质因子集合是空的数学上比较特殊但题目约定俗成把它算进去。也就是说前几个丑数依次是1, 2, 3, 4, 5, 6, 8, 9, 10, 12……看到这里你会发现一个关键信息丑数序列并不是 1 到 n 里挨个数出来的而是通过不断乘以 2、3、5 生成的。这正是这道题区别于判断一个数是不是丑数那道简单题的核心点。判断单个数是否丑数只需要一直除 2、除 3、除 5最后看是不是 1 就行。但这里要你返回第 n 个丑数n 的范围能到 1690题目原始约束如果你从 1 开始逐个判断每判断一个数都要做质因子分解越往后的丑数越稀疏效率会非常难看。所以这道题考察的本质是你能否从丑数的生成规律入手用空间换时间把暴力枚举优化成 O(n) 的递推。这道题适合谁来刷适合正在准备面试的初级、中级开发者也适合刚学动态规划、想找个不太难但很典型的题目入门的同学。它不像背包问题那样需要复杂的状态转移设计但三指针的思路一旦理解了对后续理解归并思想的变种题比如合并 K 个有序链表也有帮助。2. 暴力法为什么走不通一次失败尝试的完整复盘很多人的第一版思路是这样的从 1 开始往后遍历每个正整数写一个isUgly函数判断它是不是丑数是的话计数器加 1直到找到第 n 个。这个思路有一个非常直观的诱惑它简单零思考成本。class Solution { public int nthUglyNumber(int n) { int count 0; int num 1; while (count n) { if (isUgly(num)) { count; } num; } return num - 1; } private boolean isUgly(int num) { if (num 0) return false; int[] factors {2, 3, 5}; for (int factor : factors) { while (num % factor 0) { num / factor; } } return num 1; } }这个代码本身没有错isUgly的写法也是标准操作能被 2 整除就一直除 2能被 3 整除就一直除 3能被 5 整除就一直除 5最后剩下的如果等于 1说明它没有其他质因子就是丑数。但问题出在时间复杂度和丑数密度上。先分析isUgly的时间复杂度每次判断需要做若干次除法运算虽然在数值变大时次数不会太多大概是对数级别但关键在于isUgly被调用的次数。丑数的分布并不是均匀的越往后越稀疏。我实测了一下在 1 到 100 之间丑数有 15 个但到了 1 到 1000 之间丑数就只有 40 个左右。到了第 100 万个丑数附近前面需要遍历的普通整数大约是丑数数量的好几倍。换句话说暴力法的时间复杂度大约是O(n × log m)n 是目标第几个丑数m 是实际遍历到的最大整数这个 m 会远大于 n。我当年刷这道题的时候暴力法在小数据下跑得飞快但一旦n到 1000 以上程序就开始明显变慢。LeetCode 官方给的 n 上限是 1690暴力法在这个上限下虽然不至于完全超时但也会接近时间极限而且在面试现场面试官大概率会追问一句能不能优化——如果你只说得出暴力法这道题的分数基本就没了。暴力法的另一个问题是它没有利用已经算出来的丑数。判断一个数是不是丑数本质上还是在做质因子分解完全没有把丑数只能由丑数乘以 2、3、5 得到这个生成规律用上。这就是优化的突破口。3. 三指针推导为什么每个新丑数都是旧丑数乘以 2、3、5 得到的这是整道题最核心的部分我尽量用一个比较直觉的方式来推。先想一个问题丑数的定义是只包含质因子 2、3、5 的正整数那么一个丑数乘以 2它的质因子集合会变成什么答案是在原来的集合里加入一个 2但原来只有 2、3、5 三种质因子乘以 2 之后仍然只有 2、3、5。同理乘以 3、乘以 5 也一样。这个性质直接推出一个关键结论从丑数出发乘以 2、3、5 得到的仍然是丑数。反过来任何大于 1 的丑数都可以被 2、3、5 中的某个数整除。也就是说如果我们把丑数序列记为dp[0], dp[1], dp[2], ...那么对任意位置i 0一定存在某个更小的丑数dp[j]j i使得dp[i] dp[j] × 2或者dp[i] dp[j] × 3或者dp[i] dp[j] × 5。为什么因为dp[i]如果不是某个丑数乘以 2 得到的就是乘以 3 得到的否则就是乘以 5 得到的——总有一个因子能整除它除完之后的商依然是丑数质因子不增加嘛。这样就形成了一个递推关系每一个新丑数都来自一个旧丑数乘以 2、3、5 中的一个。那么问题就变成了从dp[0] 1出发怎么按从小到大的顺序生成后面的丑数为直观理解我用网格来表示。把丑数序列想象成三个队列的合并结果队列 A每个丑数 × 2队列 B每个丑数 × 3队列 C每个丑数 × 5初始时dp[0] 1 队列A1×2 2 队列B1×3 3 队列C1×5 5下一个丑数就是三个队列中最小的那个也就是 2。取走 2 之后把 2 放入 dp 数组同时 2 这个旧丑数的 ×2 结果进入队列 A。dp[1] 2 队列A2×2 4 队列B1×3 3 队列C1×5 5此时三个队列头部最小的是 3取出dp[2] 3 队列A2×2 4 队列B2×3 6 队列C1×5 5然后取 4dp[3] 4 队列A3×2 6 队列B2×3 6 队列C1×5 5此时队列 A 和队列 B 的头部都是 6说明出现了重复候选值。取出来一个 6 放进 dp 数组就行了但两个队列的指针都要前进否则下次还会再取到重复的 6。dp[4] 5 dp[5] 6到这里你基本已经能看出三指针的雏形了。我们不需要真的维护三个队列只需要维护三个指针p2、p3、p5分别表示下一个要乘以 2 的旧丑数在 dp 数组中的下标、下一个要乘以 3 的旧丑数下标、下一个要乘以 5 的旧丑数下标。每次比较dp[p2]*2、dp[p3]*3、dp[p5]*5三者的大小取最小值放入 dp 数组然后把所有等于这个最小值的指针都向后移动一位。这里有一个对新手来说非常容易踩的坑移动指针时必须用独立的 if不能用 if-else if-else。为什么因为可能有多个候选值相等比如上面例子中dp[p2]*2 dp[p3]*3都等于 6此时如果不把两个指针一起后移下一步还会重复计算 6导致 dp 数组里出现重复的 6序列就错了。这个细节在小数据量时看不出问题但一旦 n 变大最终结果就完全不同了。用表格把这个过程完整模拟一遍从n1到n10你会看得非常清楚ndp[n-1]p2p3p5dp[p2]*2dp[p3]*3dp[p5]*5选中的值1100023522210043533311046544421066555521166106663218910878421109109894311012101091053212121512101264216151515特别注意第 9 行到第 10 行的过程在n9选中 10 之后p2 从 4 移到 5p5 从 1 移到 2到了n10时dp[p3]*3 dp[4]*3 3*3 9已经是 15 了而dp[p5]*5 dp[2]*5 3*5 15两者相等都是 15。所以n10的丑数是 15同时 p3 和 p5 都要后移。这种多个候选相等的情况在序列里出现的频率比想象中要高所以用多个独立 if 处理是必须的。这个推导过程本质上就是把三个队列归并成一个有序序列的思路压缩成了三个指针的写法。理解了这个你不仅会写这道题还能理解为什么它的时间复杂度和空间复杂度都是 O(n)。4. 代码实现与易错点别再栽在这些细节上思路清楚了代码其实很短。我这里给出两种主流语言的实现顺带说一下我在写的过程中踩过的坑。先看 Java 版本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 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 - 1]; } }再看 Python 版本def nthUglyNumber(n: int) - int: dp [0] * n dp[0] 1 p2 p3 p5 0 for i in range(1, n): 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 - 1]代码逻辑一致核心就是三指针。接下来是几个我实际刷题时踩过的坑每个都值得你注意。第一个坑p2、p3、p5的初始值都是 0因为dp[0] 1而 1 乘以 2、3、5 分别得到 2、3、5这是序列开头的三个候选值。有的同学会把三个指针初始化为 1那就跳过了1×22这个候选直接从 2×2 开始了最终结果会错得离谱。第二个坑三个if必须是独立的不能用else if。我上面已经解释过原因但这里再强调一遍当多个候选值相等时比如dp[p2]*2 dp[p3]*3如果你只移动了 p2那么下一次循环 p3 还会再计算出同一个值dp 数组中就会出现重复最终第 n 个丑数可能比别人算出来的正确值要小因为你提前用了一个重复值占位置。我在 LeetCode 上跑的时候n7 的正确答案是 8但用else if的版本跑出来是 9因为这个错误版本在第 6 步取到了重复的 6导致后面整体偏移了一位。第三个坑n 的范围。剑指 Offer 49 原始题目的 n 大约在 1 到 1690 之间第 1690 个丑数是 2123366400 附近这个值仍然在 int 范围内。如果你做扩展题、或者 n 的约束变大比如 LeetCode 313 超级丑数那就得考虑用 long 防止溢出或者根据约束调整数据类型。虽然这道题 int 够用但面试时主动提一句当前范围 int 安全如果 n 更大需要替换为 long是加分项。第四个坑dp数组长度必须是 n索引从 0 到 n-1。有的同学喜欢开new int[n1]然后从 1 开始存也没问题但要注意返回值下标差异。我个人的习惯是从 0 开始返回dp[n-1]因为最终结果是第 n 个丑数不是下标 n。第五个坑别把三个候选值算提前量算错了。num2 dp[p2] * 2这里p2指向的是下一个要参与 ×2 的旧丑数的下标不是当前最后一个丑数的下标。如果你写成dp[i-1] * 2那你实际上只考虑了用最新生成的丑数去乘以 2、3、5这一种情况会漏掉很多更小的候选值。这个理解上的偏差很隐蔽我见过好几个同事在讨论这道题时把这里搞混。牢记每个指针是独立的它只负责自己的乘法因子。从复杂度上看这个解法的时间复杂度是 O(n)因为只有一个 for 循环每轮只做常数次比较和赋值空间复杂度是 O(n)因为要存长度为 n 的 dp 数组。相比暴力法的 O(n log m)在 n 1690 这个量级下差距可能不太明显但把 n 放大到 10 万、100 万差距就是天壤之别了。5. 更深入一点从丑数看归并思想以及题目变种理解了三指针之后你会发现它本质上是一个多路归并问题。每一路都是一个升序序列S2 1×2, 2×2, 3×2, 4×2, ...丑数序列的每个元素乘以 2S3 1×3, 2×3, 3×3, 4×3, ...丑数序列的每个元素乘以 3S5 1×5, 2×5, 3×5, 4×5, ...丑数序列的每个元素乘以 5而丑数序列就是这三路升序序列去重后的归并结果。你会发现在数据结构或算法题里多路归并是一个非常通用的思想比如合并 K 个有序链表LeetCode 23、合并两个有序数组LeetCode 88、找出第 K 小的有序矩阵元素LeetCode 378等都是同一套底层逻辑多个有序源头每次取最小/最大然后推进对应的那个源。明白这个思想之后很多题目都能举一反三。比如 LeetCode 313 超级丑数把固定的 3 个质因子2、3、5扩展成 K 个质因子组成的数组primes [2, 7, 13, 19]。解题思路几乎一样只是把三个指针扩展成 K 个指针。你可以用一个数组pointers [0] * len(primes)来记录每个质因子对应的指针位置然后每轮循环遍历 primes 里的每个质因子计算候选值找最小值最后把所有等于最小值的指针都后移。要注意的是当 K 变大时每次都遍历 primes 找最小值的复杂度是 O(nk)K 不大时没问题如果 K 很大可以用堆来优化取最小值的操作。我在面试里遇到过追问如果质因子数量很大怎么优化能说出用堆优化基本上这题就满分了。另一个变种是判断一个数是否是丑数输入一个整数判断它是否只包含 2、3、5 这三个质因子。这道题用while循环不断除就行。它和求第 n 个丑数最大的区别是判断单个数字不需要考虑序列生成而求第 n 个丑数如果不用生成法就会做大量无用功。这两个题经常放在一起被问用来考察一个候选人能不能区分单点判断和批量生成两种场景。还有一些进阶玩法比如求前 n 个丑数而不是第 n 个丑数本质上就是输出整个 dp 数组没有任何额外难度再比如求第 n 个超级丑数就是上面说的 313 题。把剑指 Offer 49 吃透这些变种题你基本不需要重新学算法思路只需要做少量代码调整。6. 图解之外我对这道题的三点体会最后说点跟代码无关、但跟刷题效率有关的东西。第一点这道题的价值不在于记住解法而在于学会从生成规律反推递推关系。我刚刚看这道题的时候第一反应是丑数序列不就是一个筛法的变种吗从 1 开始不断乘以 2、3、5把结果插入一个集合然后再取集合里最小的没处理过的数继续乘……这确实是一种解法而且思路更接近广度优先的感觉。但用优先队列实现的话时间复杂度是 O(n log n)空间复杂度略高三指针方案之所以是更优解是因为它利用了一个关键观察——每个丑数只需要被三个固定因子各乘一次指针单调向右移动不需要回头。这种单调队列的感觉是动态规划里一个非常经典的优化思路。以后你刷题遇到最小/最大生成序列的问题时可以先想想能不能用多个指针表示多个乘法因子然后归并第二点不要忽略为什么三个指针要同时移动这个细节。我在上面用整整一个小节强调了这个细节因为它是这道题真正的区分点。很多文章会直接给出答案但不会解释背后的原因——只有当你愿意把 5、6 步的手动模拟做出来才会发现候选值冲突不仅存在而且频繁出现。面试的时候如果面试官问你如果两个候选值相等怎么办你能立刻答出用多个 if 保证去重因为每个相等的候选值都必须被跳过这道题基本就算过了。第三点手写代码时建议先把三路归并的框架写在注释里再填充代码逻辑。哪怕面试时间紧也要先画出三个序列的示意确认指针移动的规则再写代码。我在实际模拟面试中发现很多候选人代码写不出来不是因为语法不会而是因为没在动手前建立清晰的状态图。这道题的状态非常清晰一个 dp 数组 三个指针只要你把状态图画出来代码就是敏感的翻译工作。顺便说一句LeetCode 上这道题的编号是 264Ugly Number II剑指 Offer 49 是同一道题换了个名字和输入输出格式。刷题的时候如果看到两个题号不要觉得奇怪内容基本一致。有的版本要求输入的是下标从 1 开始的 n有的版本可能把输入参数名改成 index但核心算法完全一样。我在刷题时通常会把同题异号的题目在笔记里列成一张对照表一方面防止重复刷题浪费时间另一方面也能看出不同出题人的表述差异。这道题和合并 K 个有序链表放在一起看特别有意思一个是把三个数列的元素按照大小关系合并成一个序列另一个是把 K 个链表的节点按照大小关系合并成一个链表。数据结构不同但算法骨骼完全一样。我自己在整理算法笔记时会把这一类题统一归到多路归并与指针推进这个主题下。如果你也在整理自己的刷题笔记建议也按算法思想而不是题目难度分类复盘效率会高很多。最后送一个实用的小技巧在本地 IDE 里手推完 dp 数组的几行之后可以顺手打印一份 dp 数组的前 20 个元素验证一下是否与题目给的标准输入输出一致。这道题的标准序列很多人背过[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24], 如果你打印出来跟这个序列不一致那说明指针移动逻辑或者去重逻辑有 bug不要急着提交代码先在本地把序列调对了再说。我见过不少候选人一上来就提交结果报错后靠着调试器一个个看变量反而浪费时间。这种能靠序列本身的性质自查的题先用打印自测是性价比最高的方式。