Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
（第 n 个丑数）
Note:
- 1 is typically treated as an ugly number.
- n does not exceed 1690.
Example:
1. 动态规划
任何一个新的丑数可以看做是一个旧的丑数乘以 2，3，5 得到的。因此可以设置三个指针，每当因为乘以一个因子而增加一个丑数时，相应的指针就后移，具体实现过程如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class :
def nthUglyNumber(self, n: int) -> int:
ugly_list = [1]
p_2, p_3, p_5 = 0, 0, 0
while len(ugly_list) < n:
num_2, num_3, num_5 = ugly_list[p_2]*2, ugly_list[p_3]*3, ugly_list[p_5]*5
min_num = min(num_2, num_3, num_5)
if num_2 == min_num:
p_2 += 1
if num_3 == min_num:
p_3 += 1
if num_5 == min_num:
p_5 +=1
ugly_list.append(min_num)
return ugly_list[-1]
|
近期评论