编写一个程序,找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例1
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明
func nthUglyNumber(n int) int {
if n == 0 {
return 1
}
dp := make([]int, n)
dp[0] = 1
idx2, idx3, idx5 := 0, 0, 0
for i := 1; i < n; i++ {
dp[i] = min(dp[idx2]*2, dp[idx3]*3, dp[idx5]*5)
if dp[i] == dp[idx2]*2 {
idx2++
}
if dp[i] == dp[idx3]*3 {
idx3++
}
if dp[i] == dp[idx5]*5 {
idx5++
}
}
return dp[n-1]
}
func min(a, b, c int) int {
if a <= b && a <= c {
return a
}
if b <= a && b <= c {
return b
}
return c
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有