题意说找到第n个Ugly Number.一个naive的办法是验证每个数,直到第n个丑数产生为止.但是这样可能会产生超时错误.
一个比较好的办法就是直接产生丑数,然后计数即可.如何找到下一个丑数呢?这个规律还真不好找.网上查阅了一些资料,才弄懂.
丑数列表可以按上面排列.注意,可能会有重复的,比如3*2和2*3.对于下一个丑数,都是将某个已有丑数乘以2或3或5,每一行都是顺序的丑数*相应的质,因此需要一个数组来记录已经出现过的丑数.将所有丑数分成三组(可能一个丑数分到多个组中 ),记录当前丑数的下标,然后选取下一个最小的丑数即可.注意这里不是else if,因为每个丑数可以分配到多个组中.