O(n) solution use deque


  • 0
    Y
    from collections import deque
    class Solution(object):
        def nthUglyNumber(self, n):
            """
            :type n: int
            :rtype: int
            """
            q2=deque([1])
            q3=deque([1])
            q5=deque([1])
            for i in range(n):
                next=min(q2[0],q3[0],q5[0])
                if next==q2[0]:
                    q2.popleft()
                if next==q3[0]:
                    q3.popleft()
                if next==q5[0]:
                    q5.popleft()
                q2.append(next*2)
                q3.append(next*3)
                q5.append(next*5)
            return next

Log in to reply
 

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