算法2

(暴力枚举) $O(n)$

保存中间结果，累乘

C++ 代码

class Solution {
public:
    int judge(int x,int y,int z){
        int min = (x<y)?x:y;
        min = (min < z)? min:z;
        return min;
    }
    int getUglyNumber(int n) {
        vector<int> v(n+1,0);
        v[1] = 1;
        int next = 1;
        int idx2 = 1;
        int idx3 = 1;
        int idx5 = 1;

        while(next < n){
            next += 1;
            int x = v[idx2] * 2;
            int y = v[idx3] * 3;
            int z = v[idx5] * 5;
            v[next] = judge(x,y,z);
            // cout<<v[next]<<endl;
            while(v[idx2] * 2 <= v[next])
                idx2++;
            while(v[idx3] * 3 <= v[next])
                idx3++;
            while(v[idx5] * 5 <= v[next])
                idx5++;
        }
        return v[n];
    }
};