題目：
編寫一段程序來(lái)查找第 n 個(gè)超級(jí)丑數(shù)涛酗。
超級(jí)丑數(shù)是指其所有質(zhì)因數(shù)都是長(zhǎng)度為 k 的質(zhì)數(shù)列表 primes 中的正整數(shù)欺矫。
示例:
輸入: n = 12, primes = [2,7,13,19]
輸出: 32
解釋: 給定長(zhǎng)度為 4 的質(zhì)數(shù)列表 primes = [2,7,13,19]租谈，前 12 個(gè)超級(jí)丑數(shù)序列為：[1,2,4,7,8,1143,,16,19,26,28,32] 篮奄。
說(shuō)明:
1 是任何給定 primes 的超級(jí)丑數(shù)。
給定 primes 中的數(shù)字以升序排列割去。
0 < k ≤ 100, 0 < n ≤ 10^6, 0 < primes[i] < 1000 窟却。
第 n 個(gè)超級(jí)丑數(shù)確保在 32 位有符整數(shù)范圍內(nèi)。
<meta charset="utf-8">
解析概念：
質(zhì)數(shù)
質(zhì)數(shù)（prime number）又稱素?cái)?shù)呻逆，有無(wú)限個(gè)夸赫。質(zhì)數(shù)定義為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)咖城。
丑數(shù)判斷方法
首先除2茬腿，直到不能整除為止，然后除5到不能整除為止宜雀，然后除3直到不能整除為止切平。最終判斷剩余的數(shù)字是否為1，如果是1則為丑數(shù)辐董，否則不是丑數(shù)悴品。
超級(jí)丑數(shù)
超級(jí)丑數(shù)是指其所有質(zhì)因數(shù)都是長(zhǎng)度為 k 的質(zhì)數(shù)列表 primes 中的正整數(shù)。（質(zhì)因數(shù)不再是2,3,5简烘，而是給定列表prime 中的數(shù)字）
解題方法
本題在網(wǎng)上有很多種解法苔严，本人分享一種自己一步步優(yōu)化，最終通過(guò)leetcode的方法
起始思路也是參考網(wǎng)上大神孤澎，如下：
每一個(gè)新丑數(shù)邦蜜，都可以表示為一個(gè)丑數(shù)乘以質(zhì)因數(shù)數(shù)組中的元素得到
假設(shè)我們已經(jīng)有了數(shù)組長(zhǎng)度為m的元素從小到大排列的的丑數(shù)數(shù)組，那么下一個(gè)滿足條件的丑數(shù)應(yīng)該如何得到呢亥至？其實(shí)無(wú)非就是利用上述規(guī)則：
將已經(jīng)有的丑數(shù)數(shù)組中每一個(gè)元素乘以primes質(zhì)因數(shù)數(shù)組，得到一堆新的丑數(shù)贱迟，從其中挑選出比現(xiàn)有的丑數(shù)數(shù)組大的最少的那一個(gè)元素姐扮，就是下一個(gè)滿足條件的丑數(shù)
說(shuō)到這其實(shí)我們已經(jīng)可以寫出一個(gè)滿足題意的代碼了，缺點(diǎn)就是還是不滿足時(shí)長(zhǎng)限制（本人親測(cè)）衣吠，于是參考了劍指offer茶敏，在此基礎(chǔ)上又做了一步改進(jìn)。
改進(jìn)的點(diǎn)就是不再是將所有的丑數(shù)都乘以primes質(zhì)因數(shù)數(shù)組缚俏，而是新增兩個(gè)和primes等長(zhǎng)的數(shù)組惊搏，分別叫 idxPri贮乳、numPri
idxPri數(shù)組中元素滿足如下條件：
ugly[ idxPri[i] - 1 ] * primes[i] <= ugly[ ugly.length-1 ]
numPri數(shù)組中元素為
numPri[i] = ugly[ idxPri[i] ] * primes[i]
有了這兩個(gè)數(shù)組，每次我們找下一個(gè)丑數(shù)的時(shí)候都是找對(duì)于primes中的每一個(gè)質(zhì)因子恬惯，乘以 ugly 中哪一個(gè)丑數(shù)元素比ugly中最大的丑數(shù)剛好大一點(diǎn)向拆。找到這個(gè)丑數(shù)元素的下標(biāo)我們將其存儲(chǔ)到idxPri中，存儲(chǔ)下標(biāo)與primes對(duì)應(yīng)上酪耳，并把每一個(gè)質(zhì)因子所產(chǎn)生的比ugly最大丑數(shù)大一點(diǎn)的那個(gè)丑數(shù)也按對(duì)應(yīng)下標(biāo)存到numPri中浓恳，對(duì)比numPri中誰(shuí)最小，誰(shuí)就應(yīng)該是下一個(gè)丑數(shù)碗暗。
循環(huán)此過(guò)程颈将，直到ugly長(zhǎng)度達(dá)到n
具體代碼如下
var nthSuperUglyNumber = function(n, primes) {
var ugly = [1]
var idxPri = new Array( primes.length ).fill(0)
var numPri = new Array( primes.length )
var last = ugly[ ugly.length-1 ]
while( n !== ugly.length ){
for( var i = 0 ; i < idxPri.length ; i++ ){
while( ugly[ idxPri[i] ] * primes[i] <= last ) {
idxPri[i]++;
}
}
for( var i= 0 ; i < idxPri.length ; i++ ){
numPri[i] = ugly[ idxPri[i] ] * primes[i]
}
ugly.push( numPri.reduce( function(a,b){ return a<b ? a : b } ) )
last = ugly[ ugly.length-1 ]
}
return last
}
劍指offer上對(duì)于這種方法解釋是以空間代價(jià)換時(shí)間代價(jià)，其實(shí)大家仔細(xì)看可以看出言疗，每次找出一個(gè)丑數(shù)過(guò)程循環(huán)的次數(shù)少了很多晴圾，但是我們又額外聲明了兩個(gè)數(shù)組，這應(yīng)該就是書上所說(shuō)的空間換時(shí)間噪奄。
