剑指 Offer 49. 丑数
本问题对应的 leetcode 原文链接：剑指 Offer 49. 丑数
对应打卡问题：【动态规划专题】剑指 Offer 49. 丑数
问题描述
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例 :
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1是丑数。n不超过1690。
解题思路
视频讲解直达： 本题视频讲解
代码实现
class Solution {
public int nthUglyNumber(int n) {
int a = 1, b = 1, c = 1;
int[] dp = new int[n+1];
dp[1] = 1;
for(int i = 2; i <= n; i++){
dp[i] = Math.min(Math.min(dp[a] * 2, dp[b] * 3), dp[c] * 5);
if(dp[i] == dp[a] * 2) a++;
if(dp[i] == dp[b] * 3) b++;
if(dp[i] == dp[c] * 5) c++;
}
return dp[n];
}
}
时间复杂度：O(n)
空间复杂度：O(n)