题解 | 丑数

丑数是指只包含质因子 2、3、5 的正整数（1 也被视为丑数）。如果你想在 Python 中求出某个丑数之后的下一个丑数，可以利用动态规划或最小堆的方法高效实现。

动态规划法

该方法利用三个指针分别生成 2、3、5 的倍数，并按顺序合并成丑数序列，时间复杂度 O(n)，空间复杂度 O(n)。

原理：

i2, i3, i5 分别指向当前可乘以 2、3、5 的位置。每次取最小值加入序列，并移动对应指针。当生成的丑数大于当前值时，即为下一个丑数。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param index int整型
# @return int整型
#
class Solution:
    def GetUglyNumber_Solution(self, index: int) -> int:
        # write code here
        ugly = [1]
        i2 = i3 = i5 = 0
        while len(ugly) < index:  # 寻找第index个丑数
            next2, next3, next5 = ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5  # 丑数之间相乘
            nxt = min(next2, next3, next5)  # 当前丑数为最小值
            ugly.append(nxt)  # 将当前丑数加入列表
            if nxt == next2:
                i2 += 1
            if nxt == next3:
                i3 += 1
            if nxt == next5:
                i5 += 1
        return ugly[-1] if index else 0  # 注意index为0的情况