LeetCode 第313题：超级丑数

📖 文章摘要

本文详细解析LeetCode第313题“超级丑数”，这是一道动态规划和多指针题目。文章提供了基于动态规划和优先队列的解决方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能分析。适合想要提升动态规划和数据结构应用能力的程序员。

核心知识点： 动态规划、多指针、优先队列、最小堆
难度等级： 中等
推荐人群： 具有基础算法知识，想要提升数据结构应用能力的程序员

题目描述

超级丑数是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个超级丑数。

题目数据保证第 n 个超级丑数在 32-bit 带符号整数范围内。

示例

示例 1：

输入：n = 12, primes = [2,7,13,19]
输出：32
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

示例 2：

输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。

提示

1 <= n <= 106
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据保证 primes[i] 是一个质数
primes 中的所有值都互不相同，且按递增顺序排列

解题思路

本题可以使用动态规划或优先队列来解决，我们这里主要介绍动态规划解法。

关键点：

使用多指针记录每个质数的使用情况
动态规划数组记录已生成的丑数
每次选择最小的下一个丑数
处理重复数字的情况

具体步骤：

初始化dp数组和指针数组
每次选择所有质数与当前指针位置乘积的最小值
更新对应的指针
重复直到找到第n个丑数

图解思路

动态规划状态分析表

状态	含义	计算方式	说明
dp[i]	第i个丑数	min(dp[p[j]] * primes[j])	j为质数索引
p[j]	质数j的指针	递增更新	指向下一个要使用的位置
初始状态	dp[0] = 1	-	1是最小的丑数

指针更新分析表

操作	条件	结果	说明
找最小值	所有质数计算	下一个丑数	比较所有可能的乘积
更新指针	当前乘积等于最小值	指针+1	可能多个指针同时更新
去重	重复数字	跳过	保证数组中无重复

代码实现

C# 实现

public class Solution {
    public int NthSuperUglyNumber(int n, int[] primes) {
        int m = primes.Length;
        int[] dp = new int[n];
        int[] pointers = new int[m];
        
        dp[0] = 1;
        
        for (int i = 1; i < n; i++) {
            // 找到最小的下一个丑数
            dp[i] = int.MaxValue;
            for (int j = 0; j < m; j++) {
                if ((long)dp[pointers[j]] * primes[j] < int.MaxValue) {
                    dp[i] = Math.Min(dp[i], dp[pointers[j]] * primes[j]);
                }
            }
            
            // 更新指针
            for (int j = 0; j < m; j++) {
                if ((long)dp[pointers[j]] * primes[j] == dp[i]) {
                    pointers[j]++;
                }
            }
        }
        
        return dp[n - 1];
    }
}

Python 实现

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        m = len(primes)
        dp = [1] * n
        pointers = [0] * m
        
        for i in range(1, n):
            # 找到最小的下一个丑数
            dp[i] = min(dp[p] * prime for p, prime in zip(pointers, primes))
            
            # 更新指针
            for j in range(m):
                if dp[pointers[j]] * primes[j] == dp[i]:
                    pointers[j] += 1
        
        return dp[-1]

C++ 实现

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        int m = primes.size();
        vector<int> dp(n);
        vector<int> pointers(m, 0);
        
        dp[0] = 1;
        
        for (int i = 1; i < n; i++) {
            // 找到最小的下一个丑数
            dp[i] = INT_MAX;
            for (int j = 0; j < m; j++) {
                if ((long long)dp[pointers[j]] * primes[j] < INT_MAX) {
                    dp[i] = min(dp[i], dp[pointers[j]] * primes[j]);
                }
            }
            
            // 更新指针
            for (int j = 0; j < m; j++) {
                if ((long long)dp[pointers[j]] * primes[j] == dp[i]) {
                    pointers[j]++;
                }
            }
        }
        
        return dp[n - 1];
    }
};

执行结果

C# 实现

执行用时：92 ms
内存消耗：35.2 MB

Python 实现

执行用时：156 ms
内存消耗：17.8 MB

C++ 实现

执行用时：68 ms
内存消耗：9.2 MB

性能对比

语言	执行用时	内存消耗	特点
C#	92 ms	35.2 MB	性能适中，内存占用较大
Python	156 ms	17.8 MB	执行较慢，内存占用适中
C++	68 ms	9.2 MB	执行最快，内存占用最小

代码亮点

🎯 使用动态规划高效生成丑数序列
💡 多指针技术避免重复计算
🔍 处理整数溢出的边界情况
🎨 代码结构清晰，变量命名直观

常见错误分析

🚫 未处理整数溢出问题
🚫 指针更新逻辑错误
🚫 未正确处理重复数字
🚫 初始化条件设置错误

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
动态规划	O(n*m)	O(n)	实现简单	空间消耗大
优先队列	O(nlogm)	O(n)	性能较好	实现复杂
暴力枚举	O(n²)	O(n)	直观易懂	效率低

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第313题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

动态规划状态分析表

指针更新分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流