剑指 Offer 49. 丑数

题目描述

https://leetcode-cn.com/problems/chou-shu-lcof
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12

解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/

解题思路

使用动态规划。动态规划要求我们使用一个n次循环不断在dp数组后面append一个新的丑数，最后取dp[-1]就可以得到题目所求的那个丑数。
丑数的递推性质：丑数只包含因子2，3，5，因此有“丑数” = “某之前出现过的一个合适的丑数” * “某因子”，如10 = 5 * 2。
那么这个合适的丑数怎么确定呢？最直观的方法是试试之前所有出现过的丑数，让每个丑数都分别乘以2，3，5，看看哪个乘积最小，然后填到dp数组的末尾。但是这样做复杂度太高了。
实际上我们可以定义一个三元数组[n2=某之前出现过的丑数×2, n3=某之前出现过的丑数×3, n5=某之前出现过的丑数×5]，n2 n3 n5的初始值都为1。用指针a b c指向dp数组中提到的“某之前出现过的丑数”的数组下标，初始值都为0。
每当执行一次for循环，就用三元数组的最小值分别乘以2 3 5，检查一下哪一个结果值最小，作为新的丑数，同时把对应的a/b/c自加一。为什么自加一呢？因为这样可以确保每个dp数组中出现过的丑数都有被乘以2/3/5的机会，比如dp[6]为8，当a自加到6的时候，它有幸作为16参与丑数竞选；当b自加到6的时候，它有幸作为24参与丑数竞选；当c自加到6的时候，它有幸作为40参与丑数竞选。
这样，我们可以得到下面的dp推论：
状态定义：
dp[n]为第n + 1个丑数。
初始状态：
dp[0] = [1]
a, b, c = 0, 0, 0
转移方程：
n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp * 5
select_num = min(n2, n3, n5)
dp[n] = select_num
在更新dp后，需要把与select_num对应的a/b/c加一
返回值：dp[-1]

解题代码

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp, a, b, c = [1], 0, 0, 0
        for i in range(1, n):
            n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp * 5
            # print("n2 =", n2, ", n3 =", n3, ", n5 =", n5)
            selected_num = min(n2, n3, n5)
            if selected_num == n2:
                a += 1
            # 这里不可以使用elif,不然会连续往dp数组里面加两个6(同时是2的倍数和3的倍数)
            # 如果用if,那么可以在更新a/b/c的时候,不往dp数组里面添加重复的6
            if selected_num == n3:
                b += 1
            if selected_num == n5:
                c += 1
            dp.append(selected_num)
            # print("a =", a, ", b =", b, ", c =", c)
            # print("dp数组为:", dp)
        return dp[-1]

执行结果

执行结果：通过
执行用时：160 ms, 在所有 Python3 提交中击败了45.64%
的用户内存消耗：14.9 MB, 在所有 Python3 提交中击败了34.23%的用户