Logic clear python code [Using heap: heapq ]


  • 0

    improve by induction
    0 assume ugly number UN_1 = 1
    1 UN_K = min(UN_K-12, Un_K-13, UN_k-1*5)
    2 heap will always contain first K element
    so if we do n-1th heappop,
    the last time we can get the nth ugly number

    import heapq
    class Solution(object):
        def nthUglyNumber(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n == 1:
                return 1
            heap = [1]
            for _ in range(n-1):
                k_1th = heapq.heappop(heap)
                x = k_1th*2
                y = k_1th*3
                z = k_1th*5
                #add to heap 
                #How does heapq handle duplicate ? Answer: it does not!!!!
                if x not in heap:
                    heapq.heappush(heap,x)
                if z not in heap:
                    heapq.heappush(heap,z)
                if y not in heap:
                    heapq.heappush(heap,y)
            return heapq.heappop(heap)
    

Log in to reply
 

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