313. Super Ugly Number
https://leetcode.com/problems/super-ugly-number/
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?nth?super 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 <= 1061 <= primes.length <= 1002 <= primes[i] <= 1000primes[i]?is?guaranteed?to be a prime number.- All the values of?
primes?are?unique?and sorted in?ascending order.
【C++】
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
int i, j, k = primes.size();
vector<long> idx(k,1);
vector<long long> dp(n+1, LONG_LONG_MAX);
dp[1] = 1;
for (i = 2; i <= n; ++i) {
for (j = 0; j < k; ++j) {
long long tmp = dp[idx[j]]*primes[j];
if (tmp < dp[i]) {dp[i] = tmp;}
}
for(j = 0; j < k; ++j) {
if(dp[i] == dp[idx[j]]*primes[j]) {idx[j]++;}
}
}
return dp[n];
}
};【Java】
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int i, j, k = primes.length;
int[] idx = new int[k];
Arrays.fill(idx, 1);
int[] dp = new int[n+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[1] = 1;
for (i = 2; i <= n; ++i) {
for (j = 0; j < k; ++j) {
int tmp = dp[idx[j]]*primes[j];
if (tmp < dp[i]) {dp[i] = tmp;}
}
for(j = 0; j < k; ++j) {
if (dp[i] == dp[idx[j]]*primes[j]) {idx[j]++;}
}
}
return dp[n];
}
}参考文献
【1】丑数_百度百科
