33 丑数

题目描述

把只包含质因子因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做第一个丑数。求按从小到大的顺序的第N个丑数。

解题思路

核心思想：动态规划。丑数一定是某个较小丑数乘以2、3或5得到的。

关键步骤：

维护三个指针，分别指向乘以2、3、5的丑数
每次取三个乘积的最小值作为下一个丑数
如果下一个丑数是某个乘积，对应指针+1

时间复杂度：O(n) 空间复杂度：O(n)

Python 实现

python

def get_ugly_number(index):
    """
    获取第index个丑数

    Args:
        index: 第几个丑数

    Returns:
        int: 第index个丑数
    """
    if index <= 0:
        return 0

    ugly = [0] * index
    ugly[0] = 1

    i2, i3, i5 = 0, 0, 0
    next_ugly_index = 1

    while next_ugly_index < index:
        # 计算下一个丑数
        next_ugly = min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5)
        ugly[next_ugly_index] = next_ugly

        # 更新指针
        if ugly[i2] * 2 == next_ugly:
            i2 += 1
        if ugly[i3] * 3 == next_ugly:
            i3 += 1
        if ugly[i5] * 5 == next_ugly:
            i5 += 1

        next_ugly_index += 1

    return ugly[index - 1]


# 测试代码
if __name__ == "__main__":
    print("前15个丑数:")
    for i in range(1, 16):
        print(f"第{i}个丑数: {get_ugly_number(i)}")

    print(f"\n第10个丑数: {get_ugly_number(10)}")
    print(f"第1500个丑数: {get_ugly_number(1500)}")

# 输出:
# 前15个丑数:
# 第1个丑数: 1
# 第2个丑数: 2
# 第3个丑数: 3
# 第4个丑数: 4
# 第5个丑数: 5
# 第6个丑数: 6
# 第7个丑数: 8
# 第8个丑数: 9
# 第9个丑数: 10
# 第10个丑数: 12
# 第11个丑数: 15
# 第12个丑数: 16
# 第13个丑数: 18
# 第14个丑数: 20
# 第15个丑数: 24
#
# 第10个丑数: 12
# 第1500个丑数: 859963392

图解

丑数生成过程:
ugly = [1], i2=i3=i5=0

next_ugly = min(1*2, 1*3, 1*5) = 2
ugly = [1, 2], i2=1, i3=0, i5=0

next_ugly = min(2*2, 1*3, 1*5) = 3
ugly = [1, 2, 3], i2=1, i3=1, i5=0

next_ugly = min(2*2, 2*3, 1*5) = 4
ugly = [1, 2, 3, 4], i2=2, i3=1, i5=0

next_ugly = min(3*2, 2*3, 1*5) = 5
ugly = [1, 2, 3, 4, 5], i2=2, i3=1, i5=1

next_ugly = min(3*2, 2*3, 2*5) = 6
ugly = [1, 2, 3, 4, 5, 6], i2=3, i3=2, i5=1

...继续生成

前10个丑数: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12

33 丑数 ​

题目描述 ​

解题思路 ​

Python 实现 ​

图解 ​

33 丑数

题目描述

解题思路

Python 实现

图解