- Ugly Number II
LC: 264
Ugly number is a number that only have factors 2, 3 and 5.
Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
Example
If n=9, return 10.
Challenge
O(n log n) or O(n) time.
Notice
Note that 1 is typically treated as an ugly number.
import heapq
class Solution:
"""
@param n: An integer
@return: the nth prime number as description.
"""
def nthUglyNumber(self, n):
heap = [1]
visited = set([1])
for _ in range(n):
curr = heapq.heappop(heap)
for factor in [2, 3, 5]:
new_num = curr * factor
if new_num not in visited:
heapq.heappush(heap, new_num)
visited.add(new_num)
return curr
Time: O(nlogn)
Space: O(n)
Notes:
- key point here is use heap queue to keep all numbers in ascending order. Other than that, just think this as a BFS problem.
- small thing to notice is that
visited = set([1])has bracket around.
