📃 题目描述

题目链接：

• 剑指 Offer 49. 丑数 (opens new window)
• 264. 丑数 II (opens new window)

🔔 解题思路

丑数的递推性质： 丑数只包含因子 2, 3, 52,3,5 ，因此有 “丑数 == 某较小丑数 × 某因子” （例如：10 = 5×2）。

class Solution {
    public int nthUglyNumber(int n) {
        if (n == 1) {
            return 1;
        }

        // dp[i] 表示第 i 个丑数
        int[] dp = new int[n + 1];
        // base case
        dp[1] = 1;

        int a = 1, b = 1, c = 1;
        for (int i = 2; i <= n; i ++) {
            int n2 = dp[a] * 2;
            int n3 = dp[b] * 3;
            int n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if (dp[i] == n2) {
                a ++;
            }
            // 注意这里不能用 else if！！！相等的指针都要 +1
            if (dp[i] == n3) {
                b ++;
            }
            if (dp[i] == n5) {
                c ++;
            }
        }

        return dp[n];
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：