堆 超級(jí)丑數(shù)

題目

編寫(xiě)一段程序來(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,13,14,16,19,26,28,32] 。

說(shuō)明:

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

解題

簡(jiǎn)單分析過(guò)程：

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

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個(gè)超級(jí)丑數(shù)*/
        /*index[i]表示的是primes里面的第i個(gè)數(shù)下一個(gè)將要相乘的數(shù)在dp中的位置，
        反過(guò)來(lái)想，對(duì)于每個(gè)primes來(lái)說(shuō)，我們都需要和dp中已經(jīng)算出來(lái)的結(jié)果相乘算，
        然后取最小的那個(gè)作為新的dp元素
        索引index實(shí)際上表示是這個(gè)素?cái)?shù)已經(jīng)和dp中的哪個(gè)位置結(jié)合了，下一個(gè)位置的坐標(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;
            /*遍歷對(duì)比一下值，找出最小的，*/
            for (int j = 0; j < len; j++) {
                if (min > primes[j] * dp[index[j]]) {
                    min = primes[j] * dp[index[j]];//這個(gè)地方就是當(dāng)前質(zhì)因數(shù)和他要結(jié)合的dp
                }
            }
            dp[i] = min;
            /*那個(gè)素?cái)?shù)要乘以dp的坐標(biāo)index要加1，向后推一個(gè)位
            * 如果存在重復(fù)的值，也就是說(shuō)不同的質(zhì)因數(shù)相乘，得出來(lái)相同的結(jié)果了，
            * 我們就把這幾個(gè)位置都+1，這樣就可以避免出現(xiàn)重復(fù)的值了。
            * 你想想，假如你找到了對(duì)應(yīng)的素?cái)?shù)的index，把它加1之后就break掉，那么后面的數(shù)也可以算出這個(gè)結(jié)果，
            * 下次循環(huán)的時(shí)候，勢(shì)必會(huì)把這個(gè)重復(fù)的數(shù)當(dāng)成下一個(gè)dp，因?yàn)檫@個(gè)數(shù)肯定要比下一個(gè)丑數(shù)小
            * 所以我們?cè)趂or循環(huán)中不要加break；*/
            for (int j = 0; j < len; j++) {
                if (min == primes[j] * dp[index[j]]) {
                    index[j]++;
                }
            }


        }
        return dp[n - 1];
    }
}