My python solution is TLE, can anyone help?


  • 0
    V
    def nthSuperUglyNumber(n, primes):
        length = len (primes)
        index = [0] * length
        result = [1]
        for t in range (n-1):
            minNum = min([primes[i] * result[index[i]] for i in range(length)])
            result.append(minNum)
            for i in range(length):
                if primes[i]*result[index[i]] == minNum:
                    index[i] +=1
        return result[-1]
    

    I try the same thing in Java, and that is AC.


  • 0
    C

    you need to use a heap for getting the minNum. And you update on the index[i] numbers is taking O(k) time for each step.

    Below is my unpolished code, 792 ms. It is not very brief or fast, but makes some of these points. I used frontier as your index, and frontierSet to store current values in frontier, so checking repeated number is each O(1) for each check (though you may need to do multiple times for each update).

    class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
    
        uglies=[1]
        frontier=[]
        frontierSet=set()
        for p in primes:
            heappush(frontier, (p, p, 0)) # the result number, the prime number, and the index of basis.  (uglies[basis]*prime=result)
            frontierSet.add(p)
    
        i=1
        while i<n:
            p=heappop(frontier)
            frontierSet.remove(p[0])
    
            uglies.append(p[0])
    
    
            newBasis=p[2]+1
            while p[1]*uglies[newBasis] in frontierSet:
                newBasis+=1
    
            heappush(frontier,((p[1]*uglies[newBasis], p[1],newBasis)))
            frontierSet.add(p[1]*uglies[newBasis])
    
            i+=1
        return uglies[-1]

  • 0
    V

    Thank you so much for the answer.


Log in to reply
 

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