313. 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
int k = primes.size();
vector<int> dp(n, INT_MAX);
vector<int> pos(k);
dp[0] = 1;
for(int i = 1; i < n; i++) {
int& res = dp[i];
for(int j = 0; j < k; j++) {
res = min(res, dp[pos[j]] * primes[j]);
}
for(int j = 0; j < k; j++) {
if(dp[pos[j]] * primes[j] == res)
pos[j]++;
}
}
return dp[n - 1];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
if(n == 1) return 1;
priority_queue<long long, vector<long long>, greater<long long>> pq;
for(auto p : primes) pq.push(p);
--n;
while(--n) {
long long low = pq.top();
while(!pq.empty() and pq.top() == low) {
pq.pop();
}
for(auto& p : primes) pq.push(low * p);
}
return pq.top();
}
};
|
