剑指 Offer 49. 丑数

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

1 是丑数。
n 不超过1690。

class Solution {
public:

    int nthUglyNumber(int n) {
        if(n==0)return 0;
        vector<int> dp(n+1);
        dp[1]=1;
        int l=1,r=1,q=1;
        for(int i = 2;i<=n;i++){
            int temp = min(min(dp[l]*2,dp[r]*3),dp[q]*5);
            dp[i] = temp;
            if(temp == dp[l]*2)l++;
            if(temp == dp[r]*3)r++;
            if(temp == dp[q]*5)q++;
        }
        return dp[n];
    }
};

执行用时：
8 ms
, 在所有 C++ 提交中击败了
58.99%
的用户
内存消耗：
7.5 MB
, 在所有 C++ 提交中击败了
37.14%
的用户
通过测试用例：
596 / 596