20ms Java solution


  • 0
    K

    array fPrimes is used to store the indexes of factors which choose from calculated ugly number.
    below is my output of array fPrimes and ugly of 12 [2,7,13,19]
    [0, 0, 0, 0]
    [1, 0, 0, 0]
    [2, 0, 0, 0]
    [2, 1, 0, 0]
    [3, 2, 0, 0]
    [3, 2, 1, 0]
    [4, 2, 1, 0]
    [5, 2, 2, 0]
    [5, 2, 2, 1]
    [6, 3, 2, 1]
    [7, 3, 2, 1]
    [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]

    public int nthSuperUglyNumber(int n, int[] primes) {
            if(n==1){
                return 1;   
            }
            int[] ugly = new int[n];
            int[] fPrimes=new int[primes.length];
            for(int i=0;i<primes.length;i++){
                fPrimes[i]=0;
            }
            int f=1;  //number of fPrimes to calculate
            ugly[0]=1;
            int count=1;
            while(true){
                int index=findMinimal(ugly,primes,fPrimes,f);
                ugly[count]=primes[index]*ugly[fPrimes[index]];
                if(count==n-1)
                    return ugly[count];
                fPrimes[index]++;
                if(index==f-1)  f++;
                if(f>primes.length) f=primes.length;
                count++;
            }  
        }
        
    
        private int findMinimal(int[] ugly,int[] primes,int[] fPrimes,int size){
            int minimal=Integer.MAX_VALUE;
            int mIndex=0;
            for(int i=0;i<size;i++){
                if(primes[i]*ugly[fPrimes[i]]<minimal){
                    minimal=primes[i]*ugly[fPrimes[i]];
                    mIndex=i;
                }
                else if(primes[i]*ugly[fPrimes[i]]==minimal){ //eliminate dupulications
                    fPrimes[i]++;
                }
            }
            return mIndex;
        }
    

Log in to reply
 

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