题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。

例如 6、8 都是丑数，但 14 不是，因为它包含质因子 7。

求第 n 个丑数的值。

样例

输入：5

输出：5

注意：习惯上我们把 1 当做第一个丑数。

算法

(三路归并) $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)$

C++ 代码

class Solution {
public:
    int getUglyNumber(int n) {
        // 第一个丑数是 1
        vector<int> res(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();
    }
};