丑数

## 1 题目

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

**示例:**

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

**说明:**

* 1 是丑数。
* n 不超过 1690。

## 2 问题分析

1. **丑数的递推性质**：**丑数只包含因子 2**、**3**、**5**，**因此有 $ 丑数 = 某较小丑数 \times 某因子 $**（例如 $ 10 = 5 \times 2$）。
2. **设已知长度为 $n$ 的丑数序列 $x_1, x_2, \cdots , x_n$**，**求第 $n + 1$ 个丑数 $x_{n + 1}$**，**根据递推性质**，**丑数 $x_{n + 1}$ 只可能是以下三种情况其中之一**（索引 $a, b, c$ 为未知数）：

$$
   x_{n+1}=\left\{\begin{array}{l}x_a\times2,\;a\in\left[1,\;n\right]\\x_b\times3,\;b\in\left[1,\;n\right]\\x_c\times5,\;c\in\left[1,\;n\right]\end{array}\right.
   $$
3. **丑数递推公式**：**若索引 $a, b, c$ 满足以上条件**，**则下个丑数 $x_{n + 1}$ 为以下三种情况中的最小值**：

$$
   x_{n + 1} = min(x_a \times 2, x_b \times 3, x_c \times 5)
   $$
4. **由于 $x_{n + 1}$ 是最接近 $x_n$ 的丑数**，**因此索引 $a, b, c$ 需满足以下条件**：

$$
   x_{n+1}=\left\{\begin{array}{l}x_a\times2>x_n\geq x_{a-1}\times2,\;即 x_a\mathrm{为首个乘以}2\mathrm{后大于}x_n\mathrm{的丑数}\\x_b\times3>x_n\geq x_{b-1}\times3,\;即 x_b\mathrm{为首个乘以}3\mathrm{后大于}x_n\mathrm{的丑数}\\x_c\times5>x_n\geq x_{c-1}\times5,\;即 x_c\mathrm{为首个乘以}5\mathrm{后大于}x_c\mathrm{的丑数}\end{array}\right.
   $$

![Picture1.png](/media/202202/2022-02-10_1542480.9788386990040487.png)
5. **可设置指针 $a, b, c$ 指向首个丑数**（即 1），**循环根据递推公式得到下个丑数**，**并每轮将对应指针执行 +1 即可**。
6. 因此，可采用[动态规划](https://notebook.ricear.com/project-21/doc-87)的方法来解，具体过程如下：

1. **状态定义**：

1. **设动态规划列表 $dp$**，**其中 $dp[i]$ 表示第 $i + 1$ 个丑数**。
   2. **转移方程**：

1. **当索引 $a, b, c$ 满足以下条件时**，$dp[i]$**为三种情况的最小值**：

$$
         \left\{\begin{array}{l}dp\left[a\right]\times2>dp\left[i-1\right]\geq dp\left[a-1\right]\times2\\dp\left[b\right]\times3>dp\left[i-1\right]\geq dp\left[b-1\right]\times3\\dp\left[c\right]\times5>dp\left[i-1\right]\geq dp\left[c-1\right]\times5\end{array}\right.
         $$

$$
         dp[i] = min(dp[a] \times 2, dp[b] \times 3, dp[c] \times 5)
         $$
      2. **每轮计算 $dp[i]$ 后**，**需要更新索引 $a, b, c$ 的值**，**使其始终满足方程条件**，实现方法为**分别独立判断 $dp[i]$ 和 $dp[a] \times 2, dp[b] \times 3, dp[c] \times 5$ 的大小关系**，**若相等则将对应索引 $a, b, c$ 加 1**。
   3. **初始状态**：

1. **$dp[0] = 1$**，即**第一个丑数为 1**。
   4. **返回值**：

1. $dp[n - 1]$，即**返回第 $n$ 个丑数**。

## 3 参考代码

```java
/**
 * 剑指 Offer 49. 丑数
 * @param n 丑数的序号
 * @return  第 n 个丑数
 */
public int nthUglyNumber(int n) {
    //  dp 数组，其中 dp[i] 表示第 i + 1 个丑数
    int[] dp = new int[n];
    int a = 0, b = 0, c = 0;

//  第一个丑数为 1
    dp[0] = 1;

//  循环计算 dp[i]
    for (int i = 1; i < n; i++) {
        int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
        dp[i] = Math.min(Math.min(n2, n3), n5);
        if (dp[i] == n2) {a++;}
        if (dp[i] == n3) {b++;}
        if (dp[i] == n5) {c++;}
    }

//  返回第 n 个丑数
    return dp[n - 1];
}
```

## 参考文献

1. [剑指 Offer 49. 丑数](https://leetcode-cn.com/problems/chou-shu-lcof)。
2. [剑指 Offer 49. 丑数（动态规划，清晰图解）](https://leetcode-cn.com/problems/chou-shu-lcof/solution/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t)。