前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >264. 丑数 II

264. 丑数 II

原创
作者头像
Michel_Rolle
修改于 2021-02-19 09:56:55
修改于 2021-02-19 09:56:55
3K0
举报
文章被收录于专栏:LeetCode解题LeetCode解题

264. 丑数 II

链接

编写一个程序,找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例1

代码语言:txt
AI代码解释
复制
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明

  • 1 是丑数。
  • n 不超过1690。
代码语言:txt
AI代码解释
复制
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 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 264. 丑数 II
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档