丑数

丑数_牛客题霸_牛客网

问题简述

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

思路

• 定义三个指针 i2, i3, i5 表示下一个丑数是当前指针指向的丑数乘以对应的质因数。

• 初始时，dp = [0, 1]，三个指针都为 1。

• 则下一个丑数为 k = min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5)；

• 然后分别比较 k 和 dp[i2], dp[i3], dp[i5]，如果相等则对应指针 +1；

• 正确性证明：丑数 - 力扣官方题解

Python

class Solution:
    def GetUglyNumber_Solution(self, index: int) -> int:

        i2 = i3 = i5 = 1
        dp = [0, 1]
        for _ in range(index - 1):
            k2, k3, k5 = dp[i2] * 2, dp[i3] * 3, dp[i5] * 5
            k = min(k2, k3, k5)
            dp.append(k)
            # 这里不能用 elif
            if k == k2: i2 += 1
            if k == k3: i3 += 1
            if k == k5: i5 += 1
        return dp[index]