Solution to LeetCode 264 Ugly Number II.
LeetCode 264 | JZ 49
Ugly Number II (Medium). [LeetCode link]
Dynamic Programming. Because ugly numbers only include factor 2,3,5, we have the equation: ugly number = smaller ugly number * one of the three factors. The function is for the next number is
xn = min(xa*2, xb*3, xc*5).Time complexity O(n), space complexity O(n).
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
dp = [1] * n
a, b, c = 0,0,0
for i in range(1, n):
n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp[c] * 5
dp[i] = min(n2, n3, n5)
if dp[i] == n2: a += 1
if dp[i] == n3: b += 1
if dp[i] == n5: c += 1
return dp[-1]
- Min Heap. Time complexity O(n log n), space complexity O(n).
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
factors = [2,3,5]
seen = {1}
heap = [1]
for i in range(n-1):
cur = heapq.heappop(heap)
for f in factors:
nxt = cur * f
if nxt not in seen:
seen.add(nxt)
heapq.heappush(heap,nxt)
return heapq.heappop(heap)
