问题

输出第n个丑数。丑数：只包含质因数为2, 3, 5的数

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

算法：三路归并

容易想到，当前丑数 = 某个较小丑数 * 某个因子

关键是怎么确定是哪个较小丑数和哪个因子相乘。我们需要当前丑数是所有没出现过的丑数中最小的那个。同时，它也是2, 3, 5分别乘以已经出现的丑数中得到的乘积的最小值

为了做到这一点，我们可以用三路归并：开三个指针指向最开头的丑数1，循环每轮得到下个丑数（三个乘积中的最小值），然后将对应指针+1即可（注意：如果多个乘积都是最小值，则多个指针都要+1）。

时间复杂度

$O(N)$

代码

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> f(n+1);
        f[1] = 1;
        int a = 1, b = 1, c = 1;
        for(int i = 2; i <= n; i ++){
            int n1 = f[a] * 2;
            int n2 = f[b] * 3;
            int n3 = f[c] * 5;
            f[i] = min(n1,min(n2,n3));
            if(f[i] == n1) a ++;
            if(f[i] == n2) b ++;
            if(f[i] == n3) c ++;
        }
        return f[n];
    }
};