Java 23ms Solution (DP)


  • 0
    R
    class Solution {
        // The idea is the same as Ugly Number II, using array to store all the primeIndex in stead.
        public int nthSuperUglyNumber(int n, int[] primes) {
            int[] primeIndex = new int[primes.length]; // Store index of each number in primes
            int[] result = new int[n]; // Store ugly number from 1 ~ n
            result[0] = 1;
            
            for(int i = 1; i < n; i++) {
                int min = Integer.MAX_VALUE;
                for(int j = 0; j < primeIndex.length; j++) {
                    min = Math.min(min, result[primeIndex[j]] * primes[j]);
                }
                result[i] = min;
                for(int j = 0; j < primeIndex.length; j++) {
                    if(min == result[primeIndex[j]] * primes[j]) {
                        primeIndex[j]++;
                    }
                }
            }
            return result[n - 1];
        }
    }
    

Log in to reply
 

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