剑指 Offer 49. 丑数

解题思路：

丑数的递推性质： 丑数只包含因子2，3，5，因此有”丑数 = 某较小的丑数 × times × 某因子(2,3,5)“。

设已知长度为 n n n的丑数序列 x 1 , x 2 , ⋯   , x n x_1, x_2, cdots , x_n x1​,x2​,⋯,xn​ ，求第 n + 1 n+1 n+1 个丑数 x n + 1 x_{n+1} xn+1​。根根据递推性质，丑数 x n + 1 x_{n+1} xn+1​ 只可能是以下三种情况其中之一（索引 a , b , c a, b, c a,b,c 为未知数）：

x n + 1 = { x a × 2 x b × 3 x c × 5 begin{aligned} x_{n+1}=left{begin{matrix} x_a times 2 \ x_b times 3 \ x_c times 5 \ end{matrix}right. end{aligned} xn+1​=⎩⎨⎧​xa​×2xb​×3xc​×5​​

丑数递推公式： 若索引 a , b , c a,b,c a,b,c 满足以上条件，则下个丑数 x n + 1 x_{n+1} xn+1​ 为以下三种情况中的 最小值 ；

x n + 1 = m i n ( x a × 2 , x b × 3 , x c × ) x_{n+1} = min(x_atimes 2, x_b times 3, x_c times ) xn+1​=min(xa​×2,xb​×3,xc​×)

由于 x n + 1 x_{n+1} xn+1​是 最接近 x n x_n xn​ 的丑数，因此索引 a , b , c a, b, c a,b,c 需满足以下条件：

{ x a × 2 > x n ≥ x a − 1 × 2 , 即 x a 为 首 个 乘 以 2 后 大 于 x n 的 丑 数 x b × 3 > x n ≥ x b − 1 × 3 , 即 x b 为 首 个 乘 以 3 后 大 于 x n 的 丑 数 x c × 5 > x n ≥ x c − 1 × 5 , 即 x c 为 首 个 乘 以 5 后 大 于 x n 的 丑 数 begin{aligned} left{begin{matrix} x_a times 2 > x_n geq x_{a-1} times 2, 即x_a为首个乘以2后大于x_n的丑数\ x_b times 3 > x_n geq x_{b-1} times 3, 即x_b为首个乘以3后大于x_n的丑数 \ x_c times 5 > x_n geq x_{c-1} times 5, 即x_c为首个乘以5后大于x_n的丑数 \ end{matrix}right. end{aligned} ⎩⎨⎧​xa​×2>xn​≥xa−1​×2,即xa​为首个乘以2后大于xn​的丑数xb​×3>xn​≥xb−1​×3,即xb​为首个乘以3后大于xn​的丑数xc​×5>xn​≥xc−1​×5,即xc​为首个乘以5后大于xn​的丑数​​

因此，可设置指针 a , b , c a,b,c a,b,c 指向首个丑数（即 1 ），循环根据递推公式得到下个丑数，并每轮将对应指针执行 +1 即可。

算法解析：

• 状态定义： 设动态规划列表 d p dp dp ， d p [ i ] dp[i] dp[i]代表第 i + 1 i + 1 i+1个丑数；

• 转移方程：

  1. 当索引 a , b , c a, b, c a,b,c满足以下条件时， d p [ i ] dp[i] dp[i] 为三种情况的最小值；
  2. 每轮计算 d p [ i ] dp[i] dp[i] 后，需要更新索引 a , b , c a, b, c a,b,c的值，使其始终满足方程条件。实现方法：分别独立判断 d p [ i ] dp[i] dp[i] 和 d p [ a ] × 2 , d p [ b ] × 3 , d p [ c ] × 5 dp[a] times 2, dp[b] times 3, dp[c] times 5 dp[a]×2,dp[b]×3,dp[c]×5 的大小关系，若相等则将对应索引 a , b , c a , b , c a,b,c 加 1 ；

{ d p [ a ] × 2 > d p [ i − 1 ] ≥ d p [ a − 1 ] × 2 d p [ b ] × 3 > d p [ i − 1 ] ≥ d p [ b − 1 ] × 3 d p [ c ] × 5 > d p [ i − 1 ] ≥ d p [ c − 1 ] × 5 d p [ i ] = m i n { d p [ a ] × 2 , d p [ b ] × 3 , d p [ c ] × 5 } begin{aligned} left{begin{matrix} dp[a] times 2 > dp[i-1] geq dp[a-1] times 2\ dp[b] times 3 > dp[i-1] geq dp[b-1] times 3\ dp[c] times 5 > dp[i-1] geq dp[c-1] times 5\ end{matrix}right.\ dp[i] = minbegin{Bmatrix} dp[a] times 2, dp[b] times 3, dp[c] times 5 end{Bmatrix} end{aligned} ⎩⎨⎧​dp[a]×2>dp[i−1]≥dp[a−1]×2dp[b]×3>dp[i−1]≥dp[b−1]×3dp[c]×5>dp[i−1]≥dp[c−1]×5​dp[i]=min{dp[a]×2,dp[b]×3,dp[c]×5​}​

• 初始状态： d p [ 0 ] = 1 dp[0] = 1 dp[0]=1，即第一个丑数为 1 ；
• 返回值： d p [ n − 1 ] dp[n-1] dp[n−1]，即返回第 n n n 个丑数；

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int idx1 = 0;
        int idx2 = 0;
        int idx3 = 0;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(Math.min(dp[idx1] * 2, dp[idx2] * 3), dp[idx3] * 5);
            if (dp[i] == dp[idx1] * 2) {
                idx1++;
            }
            if (dp[i] == dp[idx2] * 3) {
                idx2++;
            }
            if (dp[i] == dp[idx3] * 5) {
                idx3++;
            }
        }
        return dp[n - 1];
    }
}