剑指 Offer 49 - 丑数
# 📃 题目描述
题目链接:
# 🔔 解题思路
丑数的递推性质: 丑数只包含因子 2, 3, 52,3,5 ,因此有 “丑数 == 某较小丑数 × 某因子” (例如:10 = 5×2)。
class Solution {
public int nthUglyNumber(int n) {
if (n == 1) {
return 1;
}
// dp[i] 表示第 i 个丑数
int[] dp = new int[n + 1];
// base case
dp[1] = 1;
int a = 1, b = 1, c = 1;
for (int i = 2; i <= n; i ++) {
int n2 = dp[a] * 2;
int n3 = dp[b] * 3;
int n5 = dp[c] * 5;
dp[i] = Math.min(Math.min(n2, n3), n5);
if (dp[i] == n2) {
a ++;
}
// 注意这里不能用 else if!!!相等的指针都要 +1
if (dp[i] == n3) {
b ++;
}
if (dp[i] == n5) {
c ++;
}
}
return dp[n];
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10