欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数学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)
}

注意事项

  1. to add

说明

  1. 当前使用 go1.15.8
  2. 参考 牛客网--剑指offer
    标题中jzn(n为具体数字)代表牛客网剑指offer系列第n号题目,例如 jz01 代表牛客网剑指offer中01号题目。

注意!!!

  • 笔者最近在学习 golang,因此趁机通过数据结构和算法来进一步熟悉下go语言
  • 当前算法主要来源于剑指 offer,后续会进一步补充 LeetCode 上重要算法,以及一些经典算法
  • 此处答案仅为参考,不一定是最优解,欢迎感兴趣的读者在评论区提供更优解

上一篇:

下一篇: