Leetcode每日一题 264. 丑数 II

¶264. 丑数 II

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

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

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

提示：

• 1 <= n <= 1690

很明显，判断每一个数是否是丑数，再判断它是第几个明显不现实，绝对超时，所以要提前构造每个数的2，3，5倍，然后直到这是第n个丑数，再返回。

构造方法就是建立一个dp数组，dp[i-1]代表的这是第i个丑数，初始化dp[0] = 1,因为第一个丑数是1，然后我们使用3个下标p2=0,p3=0,p5=0，去分别代表2倍，3倍，5倍，如何构造第二个丑数呢，我们要使2dp[p2]，3dp[p3],5dp[p5],很明显，其中最小的就是第2个丑数，3dp[p3],5*[p5]一定是后面的丑数了（只对这次而言），然后p2下标加一，第三个丑数理所当然的应该是3dp[p3],算嘛，2dp[p2],3dp[p3],5dp[p5],中最小的一定是3*dp[p3]，而我们不用算，我们只需要用min来取得每次一最小的丑数就行了。

class Solution {
public:
    int nthUglyNumber(int n) {
        int p2 = 0 , p3 = 0 , p5 = 0;

        vector<int> dp(n,1);

        dp[0] = 1;
        for(int i = 1 ; i < n ; i++)
        {
            dp[i] = min(min(dp[p2]*2,dp[p3]*3),dp[p5]*5);
            if(dp[p2]*2 == dp[i])p2++; //以下三行都是防止大小相等的元素构成两个相同丑数
            if(dp[p3]*3 == dp[i])p3++;
            if(dp[p5]*5 == dp[i])p5++;
        }

        return dp[n-1];
    }

};