# c++ priority_queue solution, O( n*log(k) ), by ChaoyangHe

• This is my c++ priority_queue solution, pass all the test cases.
glad to chat with you about the code, my WeChat ID: TTHarry

``````struct Ugly{
int mVal;
int mIdx;
int mP;
Ugly(int val, int idx, int p){
mVal = val;
mIdx = idx;
mP = p;
}
};

class MyCompare{
public:
bool operator()(Ugly& u1, Ugly& u2){
return u1.mVal > u2.mVal;//min-heap
}
};
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
if(n<=0) return -1;
if(n==1) return 1;
vector<int> ugly(n, INT_MAX);
ugly[0] = 1;
priority_queue< Ugly, vector<Ugly>, MyCompare > pq;
for(int k = 0; k < primes.size(); k++) pq.push(Ugly(primes[k], 0, primes[k]));
for(int i = 1; i < n; i++){
Ugly u = pq.top();
ugly[i] = u.mVal;
while(pq.top().mVal == ugly[i]){
Ugly next = pq.top();
pq.pop();
next.mIdx++;
next.mVal = next.mP * ugly[next.mIdx];
pq.push(next);
if(pq.size() == 1) break;
}
}
return ugly[n-1];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.