0264._ugly_number_ii.md

264. Ugly Number II

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/ugly-number-ii/description/

内容描述

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:  

1 is typically treated as an ugly number.
n does not exceed 1690.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

因为deque的popleft是O(1)的，所以最终也可以做到O(N)时间

beats 61.72%

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        q2, q3, q5 = collections.deque([2]), collections.deque([3]), collections.deque([5])
        while n > 1:
            x = min(q2[0],q3[0],q5[0])
            if x == q2[0]:
                x = q2.popleft()
                q2.append(2*x)
                q3.append(3*x)
                q5.append(5*x)
            elif x == q3[0]:
                x = q3.popleft()
                q3.append(3*x)
                q5.append(5*x)
            else:
                x = q5.popleft()
                q5.append(5*x)
            n -= 1
        return x

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

更简单的版本，参考alexef大神

beats 94.32%

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        ugly = [1]
        i2, i3, i5 = 0, 0, 0
        for i in range(n-1):
            u2, u3, u5 = 2 * ugly[i2], 3 * ugly[i3], 5 * ugly[i5]
            umin = min(u2, u3, u5)
            if umin == u2:
                i2 += 1
            if umin == u3:
                i3 += 1
            if umin == u5:
                i5 += 1
            ugly.append(umin)
        return ugly[-1]