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


  • 1

    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];
        }
    };
    

Log in to reply
 

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