题目描述

我们把只包含质因子 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。

注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/

---

算法

(三路归并) $O(n)$

使用 vector<int> res 存储每个丑数，且已知第一个丑数是 $1$，即 $res[0] = 1$

用 $i, j, k$ 三个指针分别指向三个序列，$i$ 指向质因子包含 $2$ 的所有数组成的序列 $II$，$j$ 指向质因子包含 $3$ 的所有数组成的序列 $III$，$k$ 指向质因子包含 $5$ 的所有数组成的序列 $V$。初始状态下三个指针都是 $0$，指向第一个丑数 $res[0] = 1$

三路归并，每次取 $res[i] * 2, res[j] * 3, res[k] * 5$ 中的最小值，就是下一个丑数。
其中 $res[i]$ 是序列 $II$ 的第 $i$ 个数，那么 $res[i] * 2$ 就是第 $i + 1$ 个数，$res[j]$ 是序列 $III$ 的第 $j$ 个数，那么 $res[j] * 3$ 就是第 $j + 1$ 个数，$res[k]$ 是序列 $V$ 的第 $k$ 个数，那么 $res[k] * 5$ 就是第 $k + 1$ 个数
res[0] = 1 不属于任何序列

如果下一个丑数为 $res[i] * 2$，则 $i$ 指针向往后移，如果 $res[j] * 3$，则 $j$ 指针往后移，如果 $res[k] * 5$，则 $k$ 指针往后移
如果下一个丑数即是 $2$ 的倍数也是 $3$ 的倍数，那么指针 $i$ 和 $j$ 都要往后移

代码实现方式上是直接在 $res$ 数组中边扩展序列边计算丑数

时间复杂度

求第 $n$ 个丑数，已知第一个丑数是 $1$，循环 $n - 1$ 次即可求得，时间复杂度为 $O(n)$

空间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> res(1, 1); // 第一个丑数是 1
        int i = 0, j = 0, k = 0;
        while ( -- n) {
            int t = min(res[i] * 2, min(res[j] * 3, res[k] * 5));
            res.push_back(t);

            if (res[i] * 2 == t) i ++ ;
            if (res[j] * 3 == t) j ++ ;
            if (res[k] * 5 == t) k ++ ;
        }
        return res.back();
    }
};