Question

求第1500个只有2,3,5因子的数.数是从小到大排列,第一个数是1,1=2^0*3^0*5^0.不要答案，只求编程的思路。

Answer 1

我是这样想的，首先知道第一个数是1，扩展一位得到{2,3,5}
取出最小的2，扩展一位，得到{4,6,10}，合并之前剩下的数 得到{3,4,5,6,10}
取出最小的3接着扩展一位，得到{6,9,15}，合并之前剩下的数得到 {4,5,6,6,9,10,15}，注意有个重复的6
....
这样一直扩展下去，最多扩展1500次就找到第1500大小的数，每次扩展只能派生出3个数，所以存储空间也就1500*3 = 4500

用优先队列，每次取最小的数，看看跟上一次取的是不是一样大，一样的就抛弃，否则继续扩展

其实可以更优一些
首先我们思考为什么会产生重复的数？比如2*3, 3*2，因为3乘以了比它小的数2，如果一个数扩展的时候已经乘以过3了，那就不比它小的2进行扩展了。
我们可以记录当前每个数他们最大乘以过{2,3,5}里面哪一个。比如2*2这个数可以用{2,3,5}三个数扩展。2*3只能用比3大的数扩展{3,5}，乘以过5就只能用5来扩展。

这样就不会出现重复的数了。用优先队列就可以扩展出最优的解。时间复杂度Nlog(N),空间复杂度（N*3）