Compact Python solution, O(nlogn) using heap & set


  • 1
    K
    class Solution(object):
        def nthUglyNumber(self, n):
            num_heap = [1]
            num_set = set([1])
            count = 1
            while count < n:
                smallest = heapq.heappop(num_heap)
                for v in [2, 3, 5]:
                    if v * smallest not in num_set:
                        heapq.heappush(num_heap, v * smallest)
                        num_set.add(v * smallest)
                count += 1
            return num_heap[0]

Log in to reply
 

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