#leetcode簽到
Day 7
264. Ugly Number II
一開始是沒想法的 討論區的很直觀
minheap 彈出來 *2 *3 *5 就是新的ugly number
塞回去繼續做一樣的事情 + dedup就可以了

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        heap=[1]
        cnt=1
        mem={1}
        multi=[2,3,5]
        while cnt<n:
            
            k=heapq.heappop(heap)
            cnt+=1
            for i in multi:
                a=k*i
                if a not in mem:
                    heapq.heappush(heap,a)
                    mem.add(a)
        return heap[0]