算法竞赛模板

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是质因子只包含 2、3 和 5 的正整数。

1.纯暴力 挨个枚举

2.新的丑数由已经生成的丑数分别*2 *3 *5得到
有重复

3.用三个指针来进行优化,保证不会重复

class Solution {
public:
    int nthUglyNumber(int n) {
        int dp[n+1];
        dp[1] = 1;
        for(int i = 2,i2 = 1,i3 = 1,i5 = 1; i <= n; i++) {
            int a = dp[i2]*2,b = dp[i3]*3,c = dp[i5]*5;
            int d = min(min(a,b),c);
            dp[i] = d;
            if(d == a) {
                i2++;
            }
            if(d == b) {
                i3++;
            }
            if(d == c) {
                i5++;
            }
        }
        return dp[n];
    }
};