Python算法实现：寻找ugly numbers丑数

Python算法实现：寻找ugly numbers丑数

Ugly numbers是指只包含质因子2、3和5的正整数，比如1、2、3、4、5、6、8、9、10、12等。本篇文章将介绍一种用Python实现寻找ugly numbers的算法，并提供完整源代码。

算法分析：

我们可以通过动态规划（DP）的方式来解决这个问题。首先，我们定义三个指针p2、p3和p5，它们分别表示当前ugly number乘以2、3、5的位置，同时我们也定义一个ugly数组用来存储已经找到的ugly numbers。

• 将ugly数组初始化为1，p2、p3和p5都初始化为0。
• 每次从ugly[p2]*2、ugly[p3]*3和ugly[p5]*5中选取最小值，此值即为下一个ugly number。
• 如果最小值为ugly[p2]*2，则p2加1；如果最小值为ugly[p3]*3，则p3加1；如果最小值为ugly[p5]*5，则p5加1。
• 重复执行步骤2和步骤3，直到找到第n个ugly number。

完整源代码如下所示：

def getUglyNumber(n):
# 初始化ugly数组
ugly = [1] * n
# 初始化三个指针
p2, p3, p5 = 0, 0, 0
# 每次求解下一个ugly numb