【題目描述】

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對(duì)這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：主機(jī)域名、網(wǎng)站空間、營銷軟件、網(wǎng)站建設(shè)、肇慶網(wǎng)站維護(hù)、網(wǎng)站推廣。

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.

設(shè)計(jì)一個(gè)算法，找出只含素因子2，3，5 的第 n 大的數(shù)。符合條件的數(shù)如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

注意：我們可以認(rèn)為1也是一個(gè)丑數(shù)。

【題目鏈接】

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

【題目解析】

這就是多鏈表Merge Sort的一個(gè)擴(kuò)展題。

對(duì)于任意一個(gè)ugly number - K, 2*K, 3*K, 和5*K都是ugly number，所以說新的ugly number都是從已有的ugly number上，通過與{2,3,5}相乘而產(chǎn)生的。

如果

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。只要不斷把新產(chǎn)生的ugly number通過merge sort添加到原有的ugly number數(shù)組中就可以了，直到找到第N個(gè)。

【答案鏈接】

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