313. 超级丑数

🟠 🔖 数组 数学 动态规划 🔗 力扣open in new window LeetCodeopen in new window

题目

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the nthsuper ugly number.

The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

Example 2:

Input: n = 1, primes = [2,3,5]
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].

Constraints:

1 <= n <= 10^5
1 <= primes.length <= 100
2 <= primes[i] <= 1000
primes[i] is guaranteed to be a prime number.
All the values of primes are unique and sorted in ascending order.

题目大意

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 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 <= 10^5
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ，且按 递增顺序 排列

解题思路

这道题是对 丑数问题 的拓展，利用动态规划和多指针法来生成超级丑数。核心思想是不断计算当前的最小丑数并扩展出新的丑数。

定义状态：
- dp[i] 表示第 i+1 个超级丑数。
- 初始化 dp[0] = 1。
多指针数组：
- 使用一个数组 idx，idx[j] 表示质因子 primes[j] 对应的指针在 dp 中的索引位置。
- 初始时 idx = [0, 0, ..., 0]。
当前丑数的生成：
- 对每个质因子 primes[j]，计算其生成的丑数：
  uglyNums[j] = dp[idx[j]] * primes[j]。
选取最小值：
- 当前的超级丑数是 ugly = Math.min(...uglyNums)。
更新指针：
- 如果某个 uglyNums[j] 等于当前的 ugly，则增加 idx[j]，表示 primes[j] 的指针向右移动。
重复计算：
- 不断重复上述过程，直到找到第 n 个超级丑数。

复杂度分析

时间复杂度：O(n * m)，动态规划计算 n 个超级丑数，每次需要从 m 个质因子中找到最小值。
空间复杂度：O(n + m)，需要存储动态规划数组 dp 和辅助数组 idx、uglyNums。

代码

/**
 * @param {number} n
 * @param {number[]} primes
 * @return {number}
 */
var nthSuperUglyNumber = function (n, primes) {
	const m = primes.length;
	const dp = [1]; // 动态规划数组
	const idx = new Array(m).fill(0); // 每个质因子的指针
	const uglyNums = new Array(m).fill(1); // 每个质因子当前对应的丑数

	for (let i = 1; i < n; i++) {
		// 找到当前的最小丑数
		const ugly = Math.min(...uglyNums);
		dp.push(ugly);

		// 更新指针和对应丑数
		for (let j = 0; j < m; j++) {
			if (uglyNums[j] === ugly) {
				uglyNums[j] = dp[idx[j]] * primes[j];
				idx[j]++;
			}
		}
	}

	return dp[n - 1];
};

313. 超级丑数

# 313. 超级丑数

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

313. 超级丑数

题目

题目大意

解题思路

复杂度分析

代码

相关题目