数学04--丑数
程序员文章站
2024-01-04 12:23:59
...
题目概述
- 算法说明
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 - 测试用例
输入: 7
返回值: 8
解析&参考答案
- 解析
使用三个指针,分别记录乘以2的最小数,乘以3的最小数,乘以5的最小数。 - 参考答案
vim jz33.go
package main
import (
"fmt"
"math"
)
func IsUgly(n int) bool {
for n%2 == 0 {
n = n / 2
}
for n%3 == 0 {
n = n / 3
}
for n%5 == 0 {
n = n / 5
}
if n == 1 {
return true
}
return false
}
func GetUglyNumber(index int) int {
if index < 7 {
return index
}
p2, p3, p5, newNum := 0, 0, 0, 1
arr := []int{1}
for len(arr) < index {
newNum = int(math.Min(float64(arr[p2]*2), math.Min(float64(arr[p3])*3, float64(arr[p5]*5))))
if arr[p2]*2 == newNum {
p2++
}
if arr[p3]*3 == newNum {
p3++
}
if arr[p5]*5 == newNum {
p5++
}
arr = append(arr, newNum)
//fmt.Println(p2, p3, p5, newNum)
}
return newNum
}
func main() {
index := 7
result := GetUglyNumber(index)
fmt.Println(result)
}
注意事项
- to add
说明
- 当前使用 go1.15.8
- 参考 牛客网--剑指offer
标题中jzn(n为具体数字)代表牛客网剑指offer系列第n号题目,例如 jz01 代表牛客网剑指offer中01号题目。
注意!!!
- 笔者最近在学习 golang,因此趁机通过数据结构和算法来进一步熟悉下go语言
- 当前算法主要来源于剑指 offer,后续会进一步补充 LeetCode 上重要算法,以及一些经典算法
- 此处答案仅为参考,不一定是最优解,欢迎感兴趣的读者在评论区提供更优解