264. Ugly Number II （python+cpp）

题目

解法1：brutal force(TLE)

一个个判断每个数字是否ugly

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        def isugly(num):
            if num == 0:
                return False
            for i in [2,3,5]:
                while num % i == 0:
                    num /= i
                
            return num == 1
        
        count = 0
        i = 1
        while count != n:
            if isugly(i):
                count += 1
            i+=1
        return i-1

改进的思路：

关于改进的思路，leetcode官方提供的四条hint非常的有建设性：

• The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
• An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
• The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
• Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

从这里非常明确的可以得到解题思路。对于现有的每一个ugly number，可以通过与2，3，5分别相乘得到三个新的ugly number。关键点就在于如何来保持这个不断生长的list的顺序。
第一种方法自然而然就想到heap，利用最小堆来维持顺序
第二种方法是用三指针法，类似merge n sorted list的方法，我个人不认为这是个动态规划的解法，或者说不是个典型的动态规划

解法2：heap

根据现有的ugly number的顺序，从小到大与2，3，5相乘产生新的ugly number，并利用最小堆维持从小到大的顺序

from heapq import heappop,heappush
class Ugly:
    def __init__(self):
        seen = set()
        self.ugly_list = ugly_list = [] 
        heap = []
        heappush(heap,1)
    
        for _ in range(1690):
            curr_ugly = heappop(heap)
            ugly_list.append(curr_ugly)
            for i in [2,3,5]:
                next_ugly = curr_ugly*i
                if next_ugly not in seen:
                    seen.add(next_ugly)
                    heappush(heap,next_ugly)

class Solution:
    u = Ugly()
    def nthUglyNumber(self, n: int) -> int:
        return self.u.ugly_list[n-1]

解法3：三指针法

解法2中每次选择一个数都需要利用heappush，所以每次操作的复杂度较高
利用merge n个sorted list的思想，在构造新的ugly number的同时，保证每次选择最小的ugly number。用三个指针保存上一次乘以2，3，5这三个数的位置。一个关键点是，下一个ugly number一定是这三个指针所在元素与2，3，5分别乘积的最小值。仔细考虑，通过这样的方法，每个位置都分别会与2，3，5相乘一次，与方法2长生新的ugly number的思想是相同的

class Ugly:
    def __init__(self):
        self.ugly_list = ugly_list = [1]
        p2 = p3 = p5 = 0
        for _ in range(1690):
            curr_ugly = min(ugly_list[p2]*2,ugly_list[p3]*3,ugly_list[p5]*5)
            ugly_list.append(curr_ugly)
            
            if curr_ugly == ugly_list[p2]*2:
                p2 += 1
            if curr_ugly == ugly_list[p3]*3:
                p3 += 1
            if curr_ugly == ugly_list[p5]*5:
                p5 += 1

class Solution:
    u = Ugly()
    def nthUglyNumber(self, n: int) -> int:
        return self.u.ugly_list[n-1]