题目描述
思路解析
一句话答案：LeetCode 264 丑数 II 求只含质因子 2、3、5 的第 n 个数。三指针 DP：dp[i]=min(dp[p2]×2,dp[p3]×3,dp[p5]×5)，谁命中谁前移，不漏不重，时间 O(n)、空间 O(n)。
丑数 II 到底要找第几个什么数
给一个整数 n，返回第 n 个丑数。丑数是只含质因子 2、3、5 的正整数（质因子＝把一个数拆成质数相乘时用到的那些质数），约定 1 是第 1 个。从小到大数，跳过像 7 这种含别的质因子的数，题面 n=10 的第 10 个丑数是 12。难点在按顺序不漏不重地生成。
从 1 逐个试除为什么越试越亏
从 1 往上逐个数，反复除 2、3、5，能除尽就是丑数。可丑数越往后越稀疏，第 100 个已是 1536，中间大量整数被白白试除，n 一大就拖垮时间。更快的是让每个新丑数由已有丑数乘 2、3、5 按序造出来。
为什么新丑数都藏在三指针的候选里
除了 1，每个丑数都能写成某个更小的丑数乘 2、乘 3 或乘 5。把已生成的丑数按序存进 dp 数组，dp[i] 就是第 i 个丑数（dp 即动态规划，算过的存下来往后用），dp[1]=1 当起点。下一个丑数就在「已有丑数乘 2、乘 3、乘 5」的候选里。与其全乘出来排序，不如用三个指针 p2、p3、p5 记着 2、3、5 各乘到哪，起初都指向 dp[1]，每步只看 dp[p2]×2、dp[p3]×3、dp[p5]×5。
三指针凭什么不漏也不重地按序生成
每步取最小的候选填进 dp：dp[i]=min(dp[p2]×2,dp[p3]×3,dp[p5]×5)，命中的指针前移。不漏：每个丑数迟早被 ×2、×3、×5 各用一次；不重且按序：每步只取当前最小，填出来天然从小到大。
同一个数可能被两条路造出来：6 既是 3×2 也是 2×3，dp[p2]×2 与 dp[p3]×3 会同时等于 6，只填一个，但 p2、p3 都得前移——只移一个，另一个下一步又会算出 6。所以三个判断是独立的 if，谁等于最小值谁前移，可能同时移两三个。
拿 n=10 把 dp 表一格格填到 12
dp[1]=1，三指针都指向它。第 2 项 min(1×2,1×3,1×5)=2，p2 前移；第 3 项 min(2×2,1×3,1×5)=3，p3 前移；第 4 项 min(2×2,2×3,1×5)=4，p2 前移；第 5 项 min(3×2,2×3,1×5)=5，p5 前移。
第 6 项 min(3×2,2×3,2×5)=6，×2 与 ×3 同时命中，只填一次、p2 与 p3 一起前移。往后取最小：第 7 项 min(4×2,3×3,2×5)=8、第 8 项 =9、第 9 项 min(5×2,4×3,2×5)=10（×2 与 ×5 同时命中）、第 10 项 min(6×2,4×3,3×5)=12。整张表 1、2、3、4、5、6、8、9、10、12 正是前 10 个丑数。
复杂度多少，相等和 dp[1] 两处别写错
生成 n 个丑数，每个只做取最小、移指针的常数操作，O(n) 时间；dp 存下前 n 个丑数，空间 O(n)。
两个坑。一是相等时只移一个指针：多个候选同时等于最小值，得把对应指针全部前移，否则下一步会再造出同一个数，用三个独立 if、别写成 if/elif。二是 dp[1]=1 别漏：1 是第 1 个丑数、三指针的共同起点，漏了整列没法往下乘。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
三指针的作用是「不重不漏」：每个已生成的丑数都会被 ×2、×3、×5 各用一次，指针保证按顺序逐个用、不重复。
一行 dp 表，第 i 格存第 i 个丑数。三指针 p2、p3、p5 一开始都指向第 1 格。
约定第 1 个丑数就是 1，填进 dp[1]。此时 p2=p3=p5 都指向 dp[1]。
算第 2 个丑数：三个候选——p2 指 dp[1]=1，×2=2；p3 指 dp[1]=1，×3=3；p5 指 dp[1]=1，×5=5。取三者最小。
最小是 2，填进 dp[2]。命中的指针 p2 前移一格。
算第 3 个丑数：三个候选——p2 指 dp[2]=2，×2=4；p3 指 dp[1]=1，×3=3；p5 指 dp[1]=1，×5=5。取三者最小。
最小是 3，填进 dp[3]。命中的指针 p3 前移一格。
算第 4 个丑数：三个候选——p2 指 dp[2]=2，×2=4；p3 指 dp[2]=2，×3=6；p5 指 dp[1]=1，×5=5。取三者最小。
最小是 4，填进 dp[4]。命中的指针 p2 前移一格。
算第 5 个丑数：三个候选——p2 指 dp[3]=3，×2=6；p3 指 dp[2]=2，×3=6；p5 指 dp[1]=1，×5=5。取三者最小。
最小是 5，填进 dp[5]。命中的指针 p5 前移一格。
算第 6 个丑数：三个候选——p2 指 dp[3]=3，×2=6；p3 指 dp[2]=2，×3=6；p5 指 dp[2]=2，×5=10。取三者最小。
最小是 6，填进 dp[6]。命中的指针 p2、p3 各前移一格（p2、p3 同时命中，一起前移——同时被两个指针命中的数只填一次）。
算第 7 个丑数：三个候选——p2 指 dp[4]=4，×2=8；p3 指 dp[3]=3，×3=9；p5 指 dp[2]=2，×5=10。取三者最小。
最小是 8，填进 dp[7]。命中的指针 p2 前移一格。
算第 8 个丑数：三个候选——p2 指 dp[5]=5，×2=10；p3 指 dp[3]=3，×3=9；p5 指 dp[2]=2，×5=10。取三者最小。
最小是 9，填进 dp[8]。命中的指针 p3 前移一格。
算第 9 个丑数：三个候选——p2 指 dp[5]=5，×2=10；p3 指 dp[4]=4，×3=12；p5 指 dp[2]=2，×5=10。取三者最小。
最小是 10，填进 dp[9]。命中的指针 p2、p5 各前移一格（p2、p5 同时命中，一起前移——同时被两个指针命中的数只填一次）。
算第 10 个丑数：三个候选——p2 指 dp[6]=6，×2=12；p3 指 dp[4]=4，×3=12；p5 指 dp[3]=3，×5=15。取三者最小。
最小是 12，填进 dp[10]。命中的指针 p2、p3 各前移一格（p2、p3 同时命中，一起前移——同时被两个指针命中的数只填一次）。
最右 dp[10]=12 就是第 10 个丑数。整张表 1,2,3,4,5,6,8,9,10,12 正是从小到大的前 10 个丑数。
小心 7 这个「看着小却不是丑数」的坑。
两个高频追问。
参考代码
def nthUglyNumber(n): dp = [0] * (n + 1) dp[1] = 1 p2 = p3 = p5 = 1 for i in range(2, n + 1): c2, c3, c5 = dp[p2]*2, dp[p3]*3, dp[p5]*5 dp[i] = min(c2, c3, c5) if dp[i] == c2: p2 += 1 if dp[i] == c3: p3 += 1 if dp[i] == c5: p5 += 1 return dp[n]复杂度
- 时间：O(n)，生成 n 个丑数，每个 O(1)
- 空间：O(n)，dp 数组存前 n 个丑数
易错点
面试追问把动画讲成自己的话
追问为什么不能直接遍历整数逐个判断是不是丑数？
追问能推广到「只含质因子来自给定集合」吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长递增子序列
LeetCode 300 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题