题目
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
解题思路
- 使用优先队列，每次弹出最小的数，然后把这个数*2 *3 *5 加到队列中
- 三个指针p2 p3 p5，分别指向下一个ugly可能由当前的数 *2 *3 *5 构成，找到这个最小的数，并把对应的指针+1
代码
import heapq
class Solution:
def nthUglyNumber(self, n: int) -> int:
s = {1, }
q = []
num = []
heapq.heappush(q, 1)
for i in range(n):
cur = heapq.heappop(q)
num.append(cur)
for j in [2, 3, 5]:
tmp = cur * j
if tmp not in s:
s.add(tmp)
heapq.heappush(q, tmp)
return num[n - 1]
class Solution:
def nthUglyNumber(self, n: int) -> int:
num = [1]
p2 = p3 = p5 = 0
for i in range(n):
tmp = min(num[p2] * 2, num[p3] * 3, num[p5] * 5)
num.append(tmp)
if tmp == num[p2] * 2:
p2 += 1
if tmp == num[p3] * 3:
p3 += 1
if tmp == num[p5] * 5:
p5 += 1
return num[n - 1]
