【解题报告】lintcode4求第n个丑数

题意

设计一个算法,找出只含素因子2,3,5 的第 n 大的数。
符合条件的数如:1, 2, 3, 4, 5, 6, 8, 9, 10, 12…

解答

既然只有素数因子2,3,5,那么我们可以得知,第n个丑数肯定是前面某一个丑数乘以2,3,5的结果
那么,我们可以以此生成一个丑数表
但是,第n个丑数是多少呢,可以得知,是比前一个数大的最小丑数
我们设置三个计数器,记录乘2,3,5比当前最大的丑数还要大的下标
每次添加就从这三个下标的数乘2,3,5的结果中选最小的一个
如此循环,得到第n个

代码

u3coding
A software developer

Leave a Comment

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.