【題目描述】
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size?k. For example,?[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]?is the sequence of the first 12 super ugly numbers given primes =?[2, 7, 13, 19]?of size?4.
?Notice
1?is a super ugly number for any given primes.
The given numbers in primes are in ascending order.
0 < k ≤ 100, 0 < n ≤ 10^6, 0 < primes[i] < 1000
寫一個程序來找第?n?個超級丑數(shù)稠诲。
超級丑數(shù)的定義是正整數(shù)并且所有的質(zhì)數(shù)因子都在所給定的一個大小為?k?的質(zhì)數(shù)集合內(nèi)嚷往。
比如給你 4 個質(zhì)數(shù)的集合?[2, 7, 13, 19], 那么?[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]?是前 12 個超級丑數(shù)掩完。
?注意事項
1?永遠都是超級丑數(shù)不管給的質(zhì)數(shù)集合是什么胆筒。
給你的質(zhì)數(shù)集合已經(jīng)按照升序排列。
0 <?k?≤ 100, 0 <?n?≤ 10^6, 0 <?primes[i] < 1000
【題目鏈接】
www.lintcode.com/en/problem/super-ugly-number/
【題目解析】
這道題讓我們求超級丑陋數(shù)翘簇，是之前Ugly Number的延伸馋劈，質(zhì)數(shù)集合可以任意給定处铛，這就增加了難度。
由于我們不知道質(zhì)數(shù)的個數(shù)幽邓，我們可以用一個idx數(shù)組來保存當前的位置炮温，然后我們從每個子鏈中取出一個數(shù)，找出其中最小值牵舵，然后更新idx數(shù)組對應(yīng)位置柒啤，注意有可能最小值不止一個，要更新所有最小值的位置畸颅。
【參考答案】
