Python heap solution O(nlogn)

  • 3

    This Solution is not the most efficient one, but is very easy to come out with in an interview and quite self-explaining.

    class Solution:
    # @param {integer} n
    # @return {integer} 
    def nthUglyNumber(self, n):
        import heapq
        f = [1]  
        last = 0
        cnt = 0
        while cnt < n:
            i = heapq.heappop(f)
            if i <= last: continue #skip duplicates
            last = i
            cnt += 1 
            if cnt == n: return i
            heapq.heappush(f, i*2)
            heapq.heappush(f, i*3)
            heapq.heappush(f, i*5)

  • 0

    Thank you for sharing. This indeed looks very clean!

Log in to reply

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