題目來源

• 來源：力扣264

題目描述

描述：

? 編寫一個(gè)程序，找出第 n 個(gè)丑數(shù)。

? 丑數(shù)就是只包含質(zhì)因數(shù) 2, 3, 5 的正整數(shù)。

? 例如：15是3*5，9是3*3，15和9都是丑數(shù)

示例:

? 輸入: n = 10
? 輸出: 12
解釋:

? 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個(gè)丑數(shù)。
說明:

? 1 是丑數(shù)。
? n 不超過1690。

解法分析

• 題目要求：第k個(gè)丑數(shù)。所以我們需要求丑數(shù)的升序序列的獲取方式。

首先，分析丑數(shù)的獲取方式

• 由第一個(gè)丑數(shù)1，分別于三個(gè)質(zhì)因數(shù)相乘，得到三個(gè)丑數(shù)，然后排序，得到1、2、3、5.
• 然后對第二個(gè)丑數(shù)2，再次進(jìn)行一步驟的操作，得到丑數(shù)4、6、10.升序排列得到1、2、3、4、5、6、10.
• 再對第三個(gè)丑數(shù)進(jìn)行一步驟的操作，再對整體的數(shù)列進(jìn)行排序，即可得到新的丑數(shù)序列。
• 丑數(shù)既然可以通過這種方式獲得，針對題目要求，可以進(jìn)行一些修改，即可得到第k個(gè)丑數(shù)。

實(shí)現(xiàn)方式思路如下，這里舉個(gè)例子

• 對于第一個(gè)質(zhì)因數(shù)，分別和2、3、5相乘，取到最小的2，作為第二個(gè)質(zhì)因數(shù)，然后，由于1已經(jīng)和質(zhì)因數(shù)2相乘得到丑數(shù)，這時(shí)，1不需要和質(zhì)因數(shù)2再做乘法操作來獲取丑數(shù)
• 所以，第二次操作，就是1和3、5相乘，而質(zhì)因數(shù)2和第二個(gè)丑數(shù)相乘，取到最小的3作為第三個(gè)丑數(shù)，然后，由于1已經(jīng)和質(zhì)因數(shù)3相乘得到丑數(shù)，這時(shí)，1不需要和質(zhì)因數(shù)3再做乘法操作來獲取丑數(shù)
• 所以，第三次操作，就是1和5相乘，而質(zhì)因數(shù)2、3和第二個(gè)丑數(shù)相乘，取到最小的4作為第四個(gè)丑數(shù)，然后，由于2已經(jīng)和質(zhì)因數(shù)2相乘得到丑數(shù)，這時(shí)，2不需要和質(zhì)因數(shù)2再做乘法操作來獲取丑數(shù)
• 依次類推，即可依次得到丑數(shù)序列。

圖解

丑數(shù).png

算法實(shí)現(xiàn)

• 由于需要分別標(biāo)記質(zhì)因數(shù)2、3、5分別和第幾個(gè)丑數(shù)進(jìn)行乘法運(yùn)算，所以，可以定義三個(gè)指針對應(yīng)三個(gè)質(zhì)因數(shù)，指向數(shù)組中的位置。
• 這樣，每次判斷出，取到的值是和某個(gè)質(zhì)因數(shù)反應(yīng)，就可以將該質(zhì)因數(shù)對應(yīng)的指針向后移動一位。

代碼實(shí)現(xiàn)（Java）

public int nthUglyNumber(int n) {
        //定義一個(gè)數(shù)組存儲丑數(shù)序列
        int[] dp = new int[n];
        dp[0] = 1;
        int min = Integer.MAX_VALUE;
        //定義三個(gè)指針，分別對應(yīng)質(zhì)因數(shù)2、3、5.
        int i2 = 0,i3 = 0,i5 = 0;
        for (int i = 1; i < n; i++) {
            //取得最小值作為下一個(gè)丑數(shù)
            min = Math.min(dp[i2] * 2,Math.min(dp[i5] * 5,dp[i3] * 3));
            //判斷是那一個(gè)質(zhì)因數(shù)參與得到丑數(shù)，將其指針向后移動一位
            if(min == dp[i3] * 3) i3++;
            if(min == dp[i5] * 5) i5++;
            if(min == dp[i2] * 2) i2++;
            //將丑數(shù)存入丑數(shù)序列
            dp[i] = min;
        }
        return dp[n - 1];
    }