My 64 ms C++ solution beats 96.48% cppsubmissions


  • 0
    C

    Improved from the solution by 'zjh08177 '( '7 line consice O(kn) c++ solution' in the discussion )

    vector 'index': with index[j] records the last location that multiplies primes[j].
    vector 'indexVal': with indexVal records ugly[index[j]]*primes[j].
    ugly[i] updates using the smallest number in the vector 'indexVal'.

     int nthSuperUglyNumber(int n, vector<int>& primes) {
            int primesL = primes.size();
            vector<int> index(primesL, 0), ugly(n, INT_MAX);
            ugly[0]=1;
            int nextInx;
            
            vector<int> indexVal(primes);
            for(int i=1; i<n; i++){
                ugly[i] = indexVal[0];
                nextInx = 0;
                for(int j=1; j<primesL; j++){
                    if( indexVal[j] < ugly[i] ){
                        ugly[i]=indexVal[j];
                        nextInx = j;
                    }
    				else if( indexVal[j] == ugly[i] ){
    					index[j]++;
    					indexVal[j] = ugly[index[j]]*primes[j];
    				}
    			}
    			index[nextInx]++;
    			indexVal[nextInx] = ugly[index[nextInx]]*primes[nextInx];
            }
            return ugly[n-1];
        }

Log in to reply
 

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