参考文献
ref{:target=”_blank”}
丑数升级版,使用heap来寻找next最小值
类似的丑数题目{:target=”_blank”}
C++ 代码
class Solution {
public:
// primes.size 个指针
// 每次pop出一个值的时候,需要知道是从哪个primes队列中pop的,同时也需要该指针在S中的位置idx
// 上述值存在关系: val = prime * S[idx]
int nthSuperUglyNumber(int n, vector<int>& primes) {
using PII = pair<long,long>; // val-idx
// 丑数集合
vector<int> s(n);
// 丑数集合初始化
s[0] = 1;
priority_queue<PII, vector<PII>, greater<PII>> heap;
// primes 多个队列入队
for(int prime : primes)heap.push({1*prime, 0});// s[0] = 1;
// 逐个计算
for(int i=1; i<n; ){
auto t = heap.top(); heap.pop();
int val = t.first, idx = t.second;
int prime = val/s[idx];
if(val != s[i-1])s[i++] = val; // 非重复的可以拓展s集合
// 补充新元素
heap.push({(long)prime*s[idx+1], idx+1});
}
return s[n-1];
}
};