如何找到第n个丑数?
时间: 2024-06-14 20:06:43 浏览: 10
以下是找到第n个丑数的方法:
1. 使用动态规划的方法:
```python
def getNthUglyNumber(n):
ugly = [0] * n
ugly[0] = 1
i2 = i3 = i5 = 0
next_multiple_of_2 = 2
next_multiple_of_3 = 3
next_multiple_of_5 = 5
for i in range(1, n):
ugly[i] = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)
if ugly[i] == next_multiple_of_2:
i2 += 1
next_multiple_of_2 = ugly[i2] * 2
if ugly[i] == next_multiple_of_3:
i3 += 1
next_multiple_of_3 = ugly[i3] * 3
if ugly[i] == next_multiple_of_5:
i5 += 1
next_multiple_of_5 = ugly[i5] * 5
return ugly[n - 1]
n = 10
print("第", n, "个丑数是:", getNthUglyNumber(n)) # 输出:第 10 个丑数是: 12
```
2. 使用堆的方法:
```python
import heapq
def getNthUglyNumber(n):
heap = [1]
heapq.heapify(heap)
ugly = 0
for _ in range(n):
ugly = heapq.heappop(heap)
heapq.heappush(heap, ugly * 2)
heapq.heappush(heap, ugly * 3)
heapq.heappush(heap, ugly * 5)
return ugly
n = 10
print("第", n, "个丑数是:", getNthUglyNumber(n)) # 输出:第 10 个丑数是: 12
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)