java自学教程|www.konglongmei.com

作者: 简单350
查看: 122|回复: 0

more +社区更新Forums

more +随机图赏Gallery

[技术知识] 剑指Offer-32.丑数(C++/Java)

[技术知识] 剑指Offer-32.丑数(C++/Java)

[复制链接]
简单350 | 显示全部楼层 发表于: 2019-12-3 04:49:26
简单350 发表于: 2019-12-3 04:49:26 | 显示全部楼层 |阅读模式
查看: 122|回复: 0

你还没有注册,无法下载本站所有资源,请立即注册!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
题目:

把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
分析:

可以从1开始去判断每一个数是不是丑数,即判断数字是不是只能被2,3,5整除。当然这样比较耗时。
每一个丑数都是由较小的丑数乘上2或3或5来得到的,2,3,5本身就是由1乘上2,3,5而来。后面生成的丑数可以从前面的丑数分别乘上2,3,5取一个最小的即可,所乘的丑数也不用每次都从最开始遍历,设置三个指针,分别指向乘2,乘3,乘5的丑数即可,每次新出现一个丑数,更新三个指针即可,更新的条件,便是乘上2,3,5要大于当前的丑数。
程序:

C++
[code]class Solution {public:    int GetUglyNumber_Solution(int index) {        if(index
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|网站地图|java自学教程|www.konglongmei.com

GMT+8, 2020-5-27 10:59 , Processed in 0.220161 second(s), 47 queries .

快速回复 返回顶部 返回列表