题目描述
超级丑数是一个正整数,并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes,返回第 n 个超级丑数。
题目数据保证第 n 个超级丑数在 32-bit 带符号整数范围内。
样例
示例一:
输入: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]
示例二:
输入:n = 1, primes = [2, 3, 5]
输出:1
解释:1 不含质因数,因此它的所有质因数都在质数数组 primes = [2, 3, 5] 中
动态规划
建立数组 dp[i] 表示第 i + 1 个超级丑数。
生成丑数可以看成质数列表和已生成的丑数的乘积,对于每个质数列表中的数和已生成的丑数建立联系需要用到 index 数组。
第一个丑数为 1,则 dp[0] = 1。
再生成新的丑数时,取 dp[index[j]] * primes[j] 中较小的一个。
如果生成的丑数大于等于 dp[index[j]] * primes[j]时,需及时更新 index 数组。
C++ 代码
class Solution {
public:
typedef long long LL;
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<LL> dp(n, 0);
dp[0] = 1;
vector<LL> index(primes.size(), 0);
for (int i = 1; i < n; i ++ ) {
int mi = INT_MAX;
for (int j = 0; j < primes.size(); j ++ )
if (mi > dp[index[j]] * primes[j]) mi = dp[index[j]] * primes[j];
dp[i] = mi;
for (int j = 0; j < primes.size(); j ++ )
if (mi >= dp[index[j]] * primes[j]) index[j] ++ ;
}
return dp[n - 1];
}
};