力扣 – 剑指 Offer 49. 丑数

• 2022 年 1 月 11 日
• 筆記
• 动态规划, 算法与题解

题目

剑指 Offer 49. 丑数

思路1

• 丑数是只包含 2、3、5 这三个质因子的数字，同时 1 也是丑数。要计算出 n 之前全部的丑数，就必须将 n 之前的每个丑数都乘以 2、3、5，选取出最小的那个数
• 但是如果每计算一个丑数都要将之前重新遍历一遍，时间复杂度较高
• 因此我们使用动态规划，创建一个dp数组，dp[i] 代表第 i + 1 个丑数，同时状态转移方程为：
  • \[\begin{cases} dp[a]×2>dp[i−1]≥dp[a−1]×2 \\ dp[b]×3>dp[i−1]≥dp[b−1]×3 \\ dp[c]×5>dp[i−1]≥dp[c−1]×5 \end{cases}
    \]

  • \[dp[i]=\begin{matrix} min(dp[a]×2,dp[b]×3,dp[c]×5) \end{matrix}
    \]

• 先初始化第一个丑数 1，然后我们再使用三个变量 a、b、c，分别代表在数组中的位置，作用是 dp[a/b/c] 乘 2/3/5 得到丑数的结果，然后我们需要从这三个结果里面找到最小的那个丑数即为当前丑数，然后还要判断 dp[i] 和 dp[a]x2、dp[b]x3、dp[c]x5是否存在相等，若相等则将对应索引 a b c 加 1

代码

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        // 第一个丑数为1
        dp[0] = 1;
        // 从数组下标为0开始，a用于乘2，b用于乘3，c用于乘于5
        int a = 0;
        int b = 0;
        int c = 0;

        for (int i = 1; i < n; i++) {
            // 计算下标对应的丑数
            int t1 = dp[a] * 2, t2 = dp[b] * 3, t3 = dp[c] * 5;
            // 选取三个丑数中最小的一个
            dp[i] = Math.min(Math.min(t1, t2), t3);
            // 查看刚刚选取的丑数，如果相等，下标进一位
            // 这里得用三个if，因为我们不需要重复数，只要计算过了，同样可以直接跳过
            if (dp[i] == t1) {
                a++;
            }
            if (dp[i] == t2) {
                b++;
            }
            if (dp[i] == t3) {
                c++;
            }
        }

        return dp[n-1];
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)
• 空间复杂度：\(O(N)\)