Google&ACM算法寻找丑数

2017-06-18 00:18 阅读 887 次 评论 0 条

硬件的发展一直遵循着摩尔定律,内存的容量基本上18个月就会翻一番,在软件开发过程中我们允许以牺牲一定空间来优化时间性能,以尽可能地缩短软件的相应时间。此题出自剑指offer第34题。

算法要求

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

简单但不高效的解法

根据丑数的定义,丑数只能被2、3、5整除,也就是说如果一个数能被2整除,我们把它连续除以2;如果能被3整除,我们把它连续除以3,;如果能被5整除,就连续 除以5。如果最后得到的值为1,则说明这个数就是丑数。

上述算法比较简单,但是却存在一定的效率问题,当我们传入的参数稍微大一点,比如1500,在我的VS上跑了80多秒才计算出结果,因为即使不是丑数也需要执行余数和除法操作,这显然是非常不乐观的。

空间换时间的高效解法

鉴于上述算法的弊端,我们这次可以借助辅助空间来创建一个数组,存放的数据为排好序的丑数,每一个丑数都是前面的丑数的乘2、3或5而得到的。

对乘以2而言,肯定存在某一个丑数T2,排在它之前的每一个丑数乘以2得到的结果都会小于已有最大的丑数,排在它之后的丑数乘以2都会太大。我们只需要记下这个丑数的位置,在每次生成丑数的时候,去更新这个T2,对乘3乘5来说道理是相同的。

第二种方法由于需要保存已经生成的丑数,因此借助辅助空间开辟了一个数组,这道题是为了判断我们是否分析出时间效率的瓶颈,算法性相当强,值得借鉴。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:Google&ACM算法寻找丑数 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情