2018-07-09丑数
2018-07-09 本文已影响0人
_柠檬酱_
题目：设计一个算法，找出只含素因子2，3，5 的第 n 小的数。
符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
思路：
丑数，都是由较小的丑数，乘以2,3,5产生的。
但是——如果2*3没有被选取，2*5更不会被选取，因此每次只需要更新一个数字到候选数字中，替换上一个。需要记录2,3,5现在乘以到哪个丑数了。
具体：
找出最小值之后的替换 是指之前顺序排列的丑数数组的每个值。都要乘以2,3,5的比较，一开始1*2和1*3和1*5 比较，找出最小的是2，把2放进a数组，这时候替换2的数就是2*2,；比较2*2,1*3,1*5，找到最小的是3，把3放进a数组，替换3的是2*3；比较2*2,2*3,1*5，找到最小是4,4放进a数组，这时候替换的用来乘以2的数就是3即3*2。。。
这个算法是O（n）的算法。
代码：
