堆 超級丑數(shù)

題目

編寫一段程序來查找第 n 個超級丑數(shù)。

超級丑數(shù)是指其所有質(zhì)因數(shù)都是長度為 k 的質(zhì)數(shù)列表 primes 中的正整數(shù)。

示例:

輸入: n = 12, primes = [2,7,13,19]
輸出: 32 
解釋: 給定長度為 4 的質(zhì)數(shù)列表 primes = [2,7,13,19]，前 12 個超級丑數(shù)序列為：[1,2,4,7,8,13,14,16,19,26,28,32] 。

說明:

1 是任何給定 primes 的超級丑數(shù)。 給定 primes 中的數(shù)字以升序排列。 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。 第 n 個超級丑數(shù)確保在 32 位有符整數(shù)范圍內(nèi)。

解題

簡單分析過程：

大家應(yīng)該都做過丑數(shù)的題目。套路就是：為每個質(zhì)因數(shù)建立一個指針，然后再這幾個質(zhì)因數(shù)運(yùn)算的結(jié)果中，找出個最小的，然后匹配這個數(shù)是由哪個質(zhì)因數(shù)算出來的，把它的指針值+1。 這道題的套路也差不多。只不過，因為我們這次是需要把計算出來的丑數(shù)再次和primes里面的質(zhì)因數(shù)結(jié)合，算出新的丑數(shù)。算出來的丑數(shù)放在一個dp數(shù)組里。 所以，現(xiàn)在要做的事，怎么能知道每個質(zhì)因數(shù)已經(jīng)和dp中哪個位置的丑數(shù)進(jìn)行了結(jié)合，下一個要結(jié)合的位置在哪。就需要建立一個index數(shù)組，用來存放每個質(zhì)因數(shù)下一個將要結(jié)合的dp的下標(biāo)，這個下標(biāo)是從0開始的，每結(jié)合一次就+1。extra：有個細(xì)節(jié)我會在注釋里寫一下，就是如果出現(xiàn)不同的質(zhì)因數(shù)相乘，乘出來的結(jié)果是相同的，是重復(fù)的丑數(shù)，這個時候該怎么辦呢：應(yīng)該把這幾個質(zhì)因數(shù)下一個要結(jié)合的dp下標(biāo)都加1。因為只把其中一個+1的話，下一次計算的丑數(shù)一定會是剛才這個重復(fù)的丑數(shù)，你的結(jié)果中就會有很多重復(fù)的數(shù)，所以，全都加1的話就會把這個重復(fù)數(shù)給過濾掉了。 好了，現(xiàn)在就可以寫代碼了。

public class SuperUglyNumber {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int len = primes.length;
        int dp[] = new int[n];
        dp[0] = 1;
        /*梳理一下思路，dp[i]保存的是第i個超級丑數(shù)*/
        /*index[i]表示的是primes里面的第i個數(shù)下一個將要相乘的數(shù)在dp中的位置，
        反過來想，對于每個primes來說，我們都需要和dp中已經(jīng)算出來的結(jié)果相乘算，
        然后取最小的那個作為新的dp元素
        索引index實際上表示是這個素數(shù)已經(jīng)和dp中的哪個位置結(jié)合了，下一個位置的坐標(biāo)是多少 */
        int index[] = new int[len];
        /*可能存在重復(fù)的丑數(shù)，所以呢，不要在for循環(huán)里面加break，把所有的情況都+1*/
        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            /*遍歷對比一下值，找出最小的，*/
            for (int j = 0; j < len; j++) {
                if (min > primes[j] * dp[index[j]]) {
                    min = primes[j] * dp[index[j]];//這個地方就是當(dāng)前質(zhì)因數(shù)和他要結(jié)合的dp
                }
            }
            dp[i] = min;
            /*那個素數(shù)要乘以dp的坐標(biāo)index要加1，向后推一個位
            * 如果存在重復(fù)的值，也就是說不同的質(zhì)因數(shù)相乘，得出來相同的結(jié)果了，
            * 我們就把這幾個位置都+1，這樣就可以避免出現(xiàn)重復(fù)的值了。
            * 你想想，假如你找到了對應(yīng)的素數(shù)的index，把它加1之后就break掉，那么后面的數(shù)也可以算出這個結(jié)果，
            * 下次循環(huán)的時候，勢必會把這個重復(fù)的數(shù)當(dāng)成下一個dp，因為這個數(shù)肯定要比下一個丑數(shù)小
            * 所以我們在for循環(huán)中不要加break；*/
            for (int j = 0; j < len; j++) {
                if (min == primes[j] * dp[index[j]]) {
                    index[j]++;
                }
            }


        }
        return dp[n - 1];
    }
}