LeetCode 313. 超级丑数

约 4 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节
标签
数组 动态规划 数学

题目描述

✅ 313. 超级丑数

image-20260928223410658

image-20260928223410659

题意分析

超级丑数是所有质因子都来自 primes 的正整数。按数值从小到大排列、相同数值只保留一次，求第 n 项。1 没有质因子，也满足条件；题目保证所求结果在 32 位有符号整数范围内。

解法：多指针 DP

核心思路

[!blue]

用 dp[i] 保存第 i + 1 个不同的超级丑数，初始 dp[0] = 1。对每个质数 primes[j]，依次将它乘以 dp[0]、dp[1]……，会得到一条严格递增的候选序列。用 idx[j] 记录该序列下一个尚未输出的乘法位置。

每轮比较所有 dp[idx[j]] * primes[j]，取最小值作为下一项。任何大于 1 的超级丑数都可以除去一个列表中的质因子，得到更小的超级丑数；当它成为尚未输出的最小值时，这个较小因子一定已经在 dp 中，因此它一定出现在某条候选序列里。取所有序列当前头部的最小值，不会漏掉正确下一项。

同一个数可能由不同质数相乘得到。选中最小值后，必须把所有乘积等于它的 idx[j] 都加一，使每条序列的下一候选都严格大于刚输出的值。没有命中的序列保持不动，否则会跳过尚未使用的候选。这样直接合并出了递增且不重复的结果，无需额外去重集合。

先把新结果写入 dp[i]，再推进指针，后续乘法就能使用这项历史结果。虽然最终答案保证不溢出 32 位整数，未被选中的候选乘积仍可能更大，因此 Java 用 long、Go 用 int64 完成乘法和比较，再把选中的值保存到结果数组。

解题步骤

  1. 创建长度为 n 的 dp，令 dp[0] = 1，每个质数的下标都初始化为 0。
  2. 从 i = 1 开始，扫描全部质数，求当前候选乘积的最小值。
  3. 将最小值写入 dp[i]，再扫描一次，推进所有命中该值的指针。
  4. 生成 n 项后返回 dp[n - 1]；n = 1 时直接得到初始值 1。

代码实现

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)$，k 为质数个数，每项扫描 k 条候选序列两次。
  • 空间复杂度：$O(n+k)$，保存已生成序列和各流下标。

关键点总结

[!green]

  • dp 同时保存输出历史，并为各质数的候选乘法提供因子。
  • 指针指向各自序列的首个未输出值，命中最小值的全部指针必须同步推进。

易错点总结

[!yellow]

  • 只推进一个并列流，下一轮会再次输出同一值。
  • 首项保持零，所有候选都会停在零。
  • 只检查较小质数的流，会漏掉其他流更小的当前候选。

相似题目

题目 难度 关联与区别
264. 丑数 II 中等 把固定三种质因子推广到给定集合，仍需维护各因子候选并同时跳过重复值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/92590465
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！