LeetCode 313. 超级丑数
目录
题目描述
题意分析
给一个质数列表
primes，「超级丑数」指所有质因数都落在这个列表里的正整数，规定 1 也算。要求返回第n个超级丑数（按从小到大排列，n从 1 计）。定义可以等价地改写成一条构造规则：1 是超级丑数；若
x是超级丑数且p属于primes，那么x * p也是超级丑数。反过来，任何大于 1 的超级丑数都能写成「某个更小的超级丑数 × 某个 primes 中的质数」。这条双向等价是所有解法的地基——它说明整个集合可以从 1 出发、只用乘法闭包生成，不需要做任何因数分解。数据规模上
n可达 10^5，primes长度可达 100，且题目保证第n个超级丑数在 32 位整数范围内。「答案不超过 int」这句保证的是最终结果，不是中间量：生成过程中会算出超过 int 的候选乘积，必须用 64 位承接。边界包括：
n = 1时答案恒为 1；primes只有一个元素时答案是该质数的幂；不同质数的乘积撞车（比如2 * 3和3 * 2）会产生重复候选，必须去重，否则序列里会出现同一个数占两个位置。
解法：多指针 DP
核心思路
暴力做法是从 1 开始逐个整数试，对每个数反复除以
primes里的质数看能否整除到 1。在答案可以逼近 int 上界时，要试的整数数量远超 10^5，绝大多数还都不是丑数，完全不可行。瓶颈在于「先枚举再筛选」的方向错了——超级丑数在整数中极其稀疏。换成正向生成：既然每个超级丑数都是「更小的超级丑数 × 某个质数」，那就按从小到大的顺序把它们一个个造出来。问题变成：已经有序地生成了前
i个，如何 $O(k)$ 地确定第i+1个？关键观察是，对固定的质数
primes[j]，序列dp[0]*primes[j], dp[1]*primes[j], dp[2]*primes[j], ...是严格递增的。也就是说，整个候选集合可以看作k条各自有序的流，而下一个超级丑数一定是这k条流的当前头部中的最小值——这正是「合并 k 个有序序列」的结构。于是为每条流配一个指针
idx[j]，状态定义写清楚：dp[i]是第i+1小的超级丑数（下标从 0 计）；idx[j]表示质数primes[j]下一个要相乘的是dp[idx[j]]。不变量是：每轮开始时，
dp[0..i-1]是严格递增的前i个超级丑数；且对每个j，dp[idx[j]] * primes[j]是primes[j]这条流中尚未被放入dp的最小候选。转移就是
dp[i] = min{ dp[idx[j]] * primes[j] : 0 <= j < k }，然后把所有取到这个最小值的j的指针一起后移一格。「所有取到最小值的指针一起移动」是本题最容易写错也最必须讲清的一点：当
dp[idx[j]] * primes[j]在多个j上相等时（例如2 * 3与3 * 2都等于 6），如果只移动其中一个，另一条流的头部仍停在 6 上，下一轮会把 6 再选一次，dp里就出现重复值，后面所有位次全部错位。用「多路同时推进」来去重，比事后用集合过滤更省也更直接。
解题步骤
- 开长度为
k的指针数组idx（全零）和长度为n的结果数组dp，令dp[0] = 1。之所以起点是 1，是因为 1 的质因数集合为空，平凡地满足「所有质因数都在 primes 里」，而且它是整个乘法闭包的种子。- 指针初值全为 0，含义是每条流的第一个候选都是
dp[0] * primes[j] = primes[j]。之所以合理，是因为每个质数本身就是最小的、以它为因子的超级丑数。- 外层循环从
i = 1到n-1，每轮产出一个新的超级丑数。之所以能一轮出一个，是因为不变量保证了k条流的头部覆盖了「所有比dp[i-1]大的超级丑数」中的最小者。- 第一遍内层循环扫
k个候选取最小值，乘积用 64 位计算。之所以必须提升到 64 位，是因为dp[idx[j]]本身可能已接近 int 上界，再乘上质数会溢出成负数，负数会被误当成最小值而污染整个后续序列。- 把最小值写入
dp[i]，此时可以安全地转回 int。之所以安全，是因为题目保证前n个超级丑数都在 int 范围内，被选中的那个最小值必然是其中之一。- 第二遍内层循环把所有乘积等于该最小值的
j的指针加一。之所以要单独再扫一遍而不是在第一遍里顺手记录下标，是因为并列最小可能出现在多个j上，只记一个下标就会漏掉其余流，导致重复值。- 循环结束返回
dp[n-1]。以
n = 6、primes = [2, 7, 13, 19]走一遍。初始dp[0] = 1，idx = [0, 0, 0, 0]。
i = 1：候选是1*2 = 2、1*7 = 7、1*13 = 13、1*19 = 19，最小是 2。dp[1] = 2。只有j = 0取到 2，idx = [1, 0, 0, 0]。
i = 2：候选是dp[1]*2 = 4、1*7 = 7、1*13 = 13、1*19 = 19，最小 4。dp[2] = 4，idx = [2, 0, 0, 0]。
i = 3：候选是dp[2]*2 = 8、7、13、19，最小 7。dp[3] = 7，取到最小的是j = 1，idx = [2, 1, 0, 0]。
i = 4：候选是dp[2]*2 = 8、dp[1]*7 = 14、13、19，最小 8。dp[4] = 8，idx = [3, 1, 0, 0]。
i = 5：候选是dp[3]*2 = 14、dp[1]*7 = 14、13、19，最小 13。dp[5] = 13，idx = [3, 1, 1, 0]。返回
dp[5] = 13，与预期序列1, 2, 4, 7, 8, 13一致。顺带看下一轮就能看到并列的作用：
i = 6时候选是dp[3]*2 = 14和dp[1]*7 = 14并列最小，两个指针同时推进到idx = [4, 2, 1, 0]，于是 14 只被放入一次。若只推进j = 0，下一轮j = 1的头部仍是 14，14 会被重复写入。
代码实现
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int k = primes.length;
int[] idx = new int[k];
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
long min = Long.MAX_VALUE;
for (int j = 0; j < k; j++) {
min = Math.min(min, (long) dp[idx[j]] * primes[j]);
}
dp[i] = (int) min;
for (int j = 0; j < k; j++) {
if ((long) dp[idx[j]] * primes[j] == min) {
idx[j]++;
}
}
}
return dp[n - 1];
}
}
func nthSuperUglyNumber(n int, primes []int) int {
k := len(primes)
idx := make([]int, k)
dp := make([]int, n)
dp[0] = 1
for i := 1; i < n; i++ {
min := int64(1<<63 - 1)
for j := 0; j < k; j++ {
v := int64(dp[idx[j]]) * int64(primes[j])
if v < min {
min = v
}
}
dp[i] = int(min)
for j := 0; j < k; j++ {
if int64(dp[idx[j]])*int64(primes[j]) == min {
idx[j]++
}
}
}
return dp[n-1]
}
复杂度分析
- 时间复杂度：$O(nk)$，凭据是外层要生成
n个数，每生成一个都要把k条流的头部各算一遍取最小、再扫一遍推进指针，两遍内层循环都是 $O(k)$ 且不嵌套；在n = 10^5、k = 100时约 2×10^7 次乘法，可以轻松通过。- 空间复杂度：$O(n + k)$，凭据是必须保留全部已生成的丑数供后续相乘（
dp长度n），外加每个质数一个指针（idx长度k），没有其他与规模相关的结构。
关键点总结
- 集合由「种子 + 乘法闭包」定义时，正向生成一定优于反向筛选，因为满足条件的元素在整数中往往极其稀疏，枚举再判定的方向从一开始就是错的。
- 识别出「k 条各自有序的流求全局第 i 小」这个结构，是本题的核心；同样的结构还可以用优先队列实现，多指针只是它在「流的头部可由下标直接算出」时的常数更优的特化。
- 并列最小值必须让所有相关指针同时前进，这是去重的正确手段。事后用哈希集合过滤虽然也对，但要多一份内存且掩盖了问题结构。
- 状态数组既是答案也是转移的输入源，
dp[idx[j]]读的永远是已经定稿的位置，这保证了依赖方向单向、不会出现自引用。- 中间乘积要用 64 位承接，题目保证的是「答案在 int 内」而不是「中间量在 int 内」，混淆这两者会得到负数候选并污染整条序列。
- 面试视角：面试官通常先问「只有 2、3、5 时怎么做」（即 264 题），再把质数集合一般化。答题时要显式说出「多路有序流归并」的抽象，并主动比较多指针与优先队列两种实现：前者 $O(nk)$、常数小、无额外结构；后者 $O(n \log k)$，在
k很大时更优。能主动指出重复值问题并给出「同时推进」的解决办法，基本就答满了。
易错点总结
- 用
int计算dp[idx[j]] * primes[j]：用例n = 100000、primes含较大质数时，中途某个乘积超过 int 上界变成负数，负数被选为最小值，dp从该位置起全部错误。- 只推进第一个取到最小值的指针，例如在第一遍循环里记下
minIdx然后只做idx[minIdx]++：用例n = 8、primes = [2, 3]，第 6 个位置上2*3与3*2并列为 6，只推进一个会让 6 被写入两次，正确序列1,2,3,4,6,8,9,12变成1,2,3,4,6,6,8,9。- 用
if (v <= min)记录并列最小的下标后只推进最后一个：用例primes = [2, 3]，问题与上一条相同，任何「只推进一个」的写法都会产生重复。- 第二遍循环里用
dp[i]而不是min做比较，且dp[i]已被截断为 int：用例中间乘积溢出的场景，截断后的值与 64 位的min不等，所有指针都不推进，下一轮取到同样的最小值，程序陷入生成重复值的死循环。dp[0]忘记置 1 而保持默认 0：用例任意输入，第一轮所有候选都是0 * primes[j] = 0，dp全为 0，返回 0。n = 1时仍进入主循环：用例n = 1，循环条件i < 1本就不成立不会出错，但若把循环写成do-while或从i = 0开始，会覆盖掉dp[0] = 1，返回primes[0]而非 1。- 认为
primes已经有序而据此剪枝，比如只检查前几个质数：用例primes = [7, 2]，题目并不保证升序，跳过后面的元素会漏掉真正的最小候选，返回 7 而非 2。- 每轮用
Arrays.sort对候选排序取最小：用例n = 10^5、k = 100，复杂度升到 $O(nk \log k)$ 且每轮都要新建数组，在时限边缘会超时，取最小值本来只需一遍线性扫描。- 用
HashSet记录已生成的值来去重，同时仍只推进一个指针：用例primes = [2, 3]，虽然能剔除重复，但被跳过的那一轮没有产出新数，dp数组会填不满n个位置，最终返回 0。- 返回
dp[n]而非dp[n-1]：用例n = 6，直接抛数组越界异常，因为dp的合法下标只到n-1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 264. 丑数 II | 中等 | 质数固定为 2、3、5，三个指针可以手写展开，不需要通用循环 |
| 263. 丑数 | 简单 | 只做单个数的判定，反向反复整除即可，不涉及生成序列 |
| 1201. 丑数 III | 中等 | 因子不再要求闭包，改为求「能被 a、b、c 之一整除」的第 n 个，靠容斥加二分 |
| 23. 合并 K 个升序链表 | 困难 | 同样的多路归并骨架，流的头部由指针给出而非乘法算出 |
| 378. 有序矩阵中第 K 小的元素 | 中等 | 多路有序结构求第 k 小，可用堆归并也可对值域二分 |