丑数（因子只有 2 3 5 的数）

理解题意关键

如果说一个数的因子只有 2 3 5 , 那么反过来想，这个数一定是由若干个 2 3 5 相乘得到的，所以每一次只需要找出当前所有已知丑数中由2 3 5 相乘可以得到的最小的数即可。
也就是说每一个丑数，都可以由之前的丑数乘 2/3/5 得到。

具体做法

设置三个指针，初始他们都指向第一个丑数（1），每一次由 2 3 5 分别与它们指针指向的位置的元素相乘，取出最小的那一个作为下一个丑数。

丑数

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

//这里的代码借鉴了leetcode评论区中一位大佬的代码
//在三个数中取最小值上，以及对不同指针运算出相同最小值的去重上都处理的相当精妙
class Solution {
public:
    int nthUglyNumber(int n) {
        vector dp(n+1);
        dp[1]= 1;
        int p1 = 1,p2 = 1,p3 = 1;
        for(int i=2;i<=n;i++){
            int num1 = dp[p1]*2,num2 = dp[p2]*3,num3 = dp[p3]*5;
            dp[i] = min(min(num1,num2),num3); //三个数取最小值
            //最后三个指针都判断一下是否取到了自己的值，如果取到了就移动，
            //相对于我之前判断取出了哪一个指针，这样可以简单的处理相同运算结果去重问题
            if(dp[i] == num1) p1++;
            if(dp[i] == num2) p2++;
            if(dp[i] == num3) p3++;
        }
        return dp[n];
    }
};