题目链接

LeetCode

题目描述

把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 6、8 都是丑数，但 14 不是，因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。

解题思路

丑数的递推性质： 丑数只包含因子 2,3,5 ，因此有 “丑数 = 某较小丑数 × 某因子” （例如：10=5×2）。

class Solution {
public:
    int Ugly[1692];
    Solution(){
        Ugly[1] = 1;
        // t2 就是乘以2的丑数，t3就是乘以3的丑数，t5就是乘以5的丑数
        int t2 = 1, t3 = 1, t5 = 1;
        for(int i = 2; i <= 1690; i++)
        {
            // 三个丑数中选取最小的(2,3,5) 作为下一个丑数
            Ugly[i] = min(Ugly[t2]*2, min(Ugly[t3]*3, Ugly[t5]*5));
            // 第a个数已经通过乘2得到了一个新的丑数，那下个需要通过乘2得到一个新的丑数的数应该是第(a+1)个数
            if(Ugly[i] == Ugly[t2] * 2)  t2++;
            // 第 b个数已经通过乘3得到了一个新的丑数，那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数
            if(Ugly[i] == Ugly[t3] * 3)  t3++;
            // 第 c个数已经通过乘5得到了一个新的丑数，那下个需要通过乘5得到一个新的丑数的数应该是第(c+1)个数
            if(Ugly[i] == Ugly[t5] * 5)  t5++;
        }
    }
    int nthUglyNumber(int n) {
        if(n==0)
            return 0;
        return Ugly[n];
    }
};

class Solution {
    int[] ugly = new int[1691];
    Solution(){
        ugly[1] = 1;
        int a = 1, b = 1, c = 1;
        for(int i = 2; i < 1691; ++i){
            int minVal = Math.min(ugly[a]*2,Math.min(ugly[b]*3,ugly[c]*5));
            if(minVal == ugly[a]*2){
                ++a;
            } 
            if(minVal == ugly[b]*3){
                ++b;
            } 
            if(minVal == ugly[c]*5){
                ++c;
            } 
            ugly[i] = minVal;
        }
    }
    public int nthUglyNumber(int n) {
        return ugly[n];
    }
}

• 时间复杂度 O(N)： 其中 N=n ，动态规划需遍历计算 dp 列表。
• 空间复杂度 O(N) ： 长度为 N 的 dp 列表使用 O(N) 的额外空间。