Lintcode4UglyNumberIIsolution题解-创新互联

【题目描述】

Ugly number is a number that only have factors 2, 3 and 5.

Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

Notice:Note that 1 is typically treated as an ugly number.

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

注意：我们可以认为1也是一个丑数。

【题目链接】

http://www.lintcode.com/en/problem/ugly-number-ii/

【题目解析】

这就是多链表Merge Sort的一个扩展题。

对于任意一个ugly number - K, 2*K, 3*K, 和5*K都是ugly number，所以说新的ugly number都是从已有的ugly number上，通过与{2,3,5}相乘而产生的。

如果

Ugly Number:   1,    2,     3,     4,     5,     6,      8,    10,  ..........

那么           1*2   2*2    3*2    4*2    5*2    6*2    8*2    10*2 ...........*2

               1*3   2*3    3*3    4*3    5*3    6*3    8*3    10*3 .......... *3

               1*5   2*5    3*5    4*5    5*5    6*5    8*5    10*5 .......... *5

都是ugly number。只要不断把新产生的ugly number通过merge sort添加到原有的ugly number数组中就可以了，直到找到第N个。

【答案链接】

http://www.jiuzhang.com/solutions/ugly-number-ii/

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。