剑指Offer题解 - Day65

剑指 Offer 49. 丑数

力扣题目链接[1]

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

「示例:」

输入: n = 10
输出: 12
解释:1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

「说明:」

1. 1 是丑数。
2. n 不超过1690。

分析：

根据题目描述，所谓丑数，就是质因子只包含2、3、5，需要注意的是，质因子是可以重复的。

从定义我们可以得出以下结论：

• 下一个丑数，只可能是前面某个丑数乘以2，3，5得到，然后求出最小值便是下一个丑数。
• 由于不确定是哪个丑数乘以2，3，5得到下个丑数，因此可以假设：
  • 下一个丑数为n + 1，满足条件n + 1 = Math.min(a * 2, b * 3, c * 5)
  • n + 1是最接近于n的丑数，因此a * 2是首个大于n的丑数；b * 3是首个大于n的丑数；c * 5是首个大于n的丑数。

本题可以采取动态规划的方式求出最终的丑数。上述的步骤就是动态转移方程。首先来看最终代码：

动态规划

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function(n) {
    let a = 0;
    let b = 0;
    let c = 0;
    let dp = Array(n);
    dp[0] = 1;
    for (let i = 1; i < n; i++) {
        let n2 = dp[a] * 2;
        let n3 = dp[b] * 3;
        let n5 = dp[c] * 5;
        dp[i] = Math.min(n2, n3, n5);
        if(dp[i] === n2) a++;
        if(dp[i] === n3) b++;
        if(dp[i] === n5) c++;
    }
    return dp[n - 1];
};

• 时间复杂度 O(n)。
• 空间复杂度 O(n)。

分析：

初始化三个丑数索引。同时初始化第一个丑数为1。

然后分别计算三个丑数乘以2、3、5的值，并求出最小值。最小的那个数就是当前丑数。然后需要累加求出当前丑数的丑数索引，方便求出下个丑数。动态规划状态转移结束后，返回dp数组的最后一项，便是需要求的丑数。

总结

本题考查动态规划。难度系数困难。需要注意的点就是质因子可以重复，以及状态转移的逻辑。

复杂度方面，因为需要遍历来计算dp数组，所以时间复杂度是O(n) ；dp数组占用O(n) 的空间复杂度。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/9h3im5/