112ms C++ solution with explanation


  • 7
    A
    class Solution {
    public:
        int nthSuperUglyNumber(int n, vector<int>& primes) {
            vector<int> superUglyNumbers;
            superUglyNumbers.push_back(1);  // first super ugly number
            int numPrimes = primes.size();
            vector<int> idxs(numPrimes, 0);
            // add super ugly number up to nth 
            while(superUglyNumbers.size() < n)
            {
                int nextSuperUglyNumber = superUglyNumbers[idxs[0]]*primes[0];   // next super ugly number
                for(int i = 0; i < numPrimes; i++)
                {
                    nextSuperUglyNumber = min(nextSuperUglyNumber, superUglyNumbers[idxs[i]]*primes[i]);
                }
                for(int i = 0; i < numPrimes; i++)
                {
                    if(nextSuperUglyNumber == superUglyNumbers[idxs[i]]*primes[i])
                    {
                        idxs[i]++;
                    }
                }
                superUglyNumbers.push_back(nextSuperUglyNumber);
            }
            
            return superUglyNumbers[n-1];
        }
    };

  • 1
    H

    #32ms C solution

    #define MAXN (1000000+5)
    int data[MAXN];
    
    int nthSuperUglyNumber(int n, int* primes, int primesSize) {
        int ptr[105]={0};
        int value[105];
        int min_value;
        int cnt = 1;
        data[0] = 1;
        for(int i=0;i<primesSize;i++)
            value[i] = primes[i];
        while(cnt <= n)
        {
            min_value = 0x7fffffff;
            for(int i=0; i< primesSize;i++)
                 if(min_value > value[i])
                     min_value = value[i];
            data[cnt++] = min_value;
            for(int i = 0; i < primesSize;i++)
                if(value[i] == min_value)
                {
                    value[i] = primes[i] * data[++ptr[i]];
                    if(value[i] <= 0)
                         value[i] = 0x7fffffff;
                }
                
         }
        return data[n-1];
     }

  • 0
    A

    C style is so fast


  • 0
    F

    Could it be optimized to avoid the second 'for loop'? Maybe by updating the value[i] on the first loop if value[i] == min_value, because that would mean that there is a duplicate and is ok to advance.

    What do you think?


  • 0
    H

    Yeah,it's faster!20ms.

    #define MAXN (1000000+5)
    int data[MAXN]={1};
    
    int nthSuperUglyNumber(int n, int* primes, int primesSize) {
    int ptr[105]={0}, value[105];
    int min_value, last = 1, cnt = 1;
    memcpy(value,primes,sizeof(int)*primesSize);
    while(cnt < n)
    {
        min_value = INT_MAX;
        for(int i = 0; i < primesSize; i++)
        {
            if(value[i] <= last)
                value[i] = primes[i] * data[++ptr[i]];
            if(min_value > value[i])
                min_value = value[i];
        }
        data[cnt++] = last = min_value;
    }
    return data[n-1];
    }

  • 0
    H

    Actually,using heap will be faster! The complexity will be O(n*log(primesSize)),However ,using priority queue in C++ is slower! Maybe to implement it myself is a good way.


  • 0
    D

    @AllenYick
    I have tried to copy/paste your code but failed. It seems your initial value after while loop should be
    "
    int nextSuperUglyNumber = INT_MAX;
    "


Log in to reply
 

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