Simple addiction logic to reduce the runtime. 28ms and beats 99.77%


  • 1
    E
    public class Solution {
    //this solution is developed by the idea of the following article: http://www.geeksforgeeks.org/ugly-numbers/
    //I did a very sample improvement to reduce the run-time. 
    //The improvement is to return the current minimum value of the new generated ugly number and the index to the 
    //prime number which generates the new ugly number.
    //Now we can update the index array base on the return index of the prime number.
    
    public int nthSuperUglyNumber(int n, int[] primes) {
        if(n==0 || primes==null || primes.length==0){
            return 0;
        }
        
        int[] res = new int[n]; //hold the result
        res[0]=1; //first result is always 1
        
        int primeSize = primes.length;
        int[] index = new int[primeSize]; //index point to the value in "res". 
                                            //It will use to generate the ugly number
        int[] values = new int[primeSize]; //hold the new generated ugly numbers
        
        //now fill up the result array
        for(int i=1; i<n; i++){
            //calculate ugly numbers and store them into values array
            for(int j=0; j<primeSize; j++){
                values[j]=res[index[j]]*primes[j];
            }
            
            //find the min and insert to the result;
            Pair minPair = getMin(values);
            res[i]=minPair.value;
            //update the index. this is the simple trick to reduce the run-time
            for(int j=minPair.index; j<primeSize; j++){
                if(minPair.value == values[j]){
                    index[j]++;
                }
            }
            
        }
        
        return res[n-1];
    }
    
    //find the minimum ugly numbers in the new generated ugly numbers list 
    private Pair getMin(int[] values ){
        int res = Integer.MAX_VALUE;
        int index=0;
        for(int i=0; i<values.length; i++){
            if(values[i]<res){
                res=values[i];
                index=i;
            }
        }
        return new Pair(index, res);
    }
    
    //private class to hold the minimum values and the index to the prime number
    private class Pair{
        protected int index;
        protected int value;
        
        public Pair(int index, int value){
            this.index=index;
            this.value=value;
        }
    }
    

    }


  • 0
    A

    Interesting, I implement your core improvement in my CPP code, but runtime have no change. it's still 100ms and 90.62%. May be it is because you use C and my CPP code have the extra cost when using vectors?

    int nthSuperUglyNumber(int n, vector<int>& primes) {
    	int sz = primes.size();
    	vector<int> idxs(sz, 1);
    	vector<int> v(n + 1);v[1] = 1;
    	vector<int> tmps(sz);
    	for (int i = 2;i <= n;i++) {
    		int m = INT_MAX; int minj = INT_MAX;
    		for (int j = 0;j < sz;j++) {
    			tmps[j] = v[idxs[j]] * primes[j];
    			if (tmps[j] < m) {
    				m = tmps[j];
    				v[i] = m; minj = j;
    			}
    		}
    
    		for (int j = minj;j < sz;j++) {
    			if (m == tmps[j]) {
    				idxs[j] = idxs[j] + 1;
    			}
    		}
    	}
    	return v[n];
    }

Log in to reply
 

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