題目來源

題目描述

描述：

編寫一個程式，找出第 n 個醜數。

醜數就是隻包含質因數 2， 3， 5 的正整數。

例如：15是3*5，9是3*3，15和9都是醜數

示例：

輸入： n = 10 輸出： 12 解釋：

1， 2， 3， 4， 5， 6， 8， 9， 10， 12 是前 10 個醜數。 說明：

1 是醜數。 n 不超過1690。

解法分析

題目要求：第k個醜數。所以我們需要求醜數的升序序列的獲取方式。

首先，分析醜數的獲取方式

由第一個醜數1，分別於三個質因數相乘，得到三個醜數，然後排序，得到1、2、3、5。

然後對第二個醜數2，再次進行一步驟的操作，得到醜數4、6、10。升序排列得到1、2、3、4、5、6、10。

再對第三個醜數進行一步驟的操作，再對整體的數列進行排序，即可得到新的醜數序列。

醜數既然可以透過這種方式獲得，針對題目要求，可以進行一些修改，即可得到第k個醜數。

實現方式思路如下，這裡舉個例子

對於第一個質因數，分別和2、3、5相乘，取到最小的2，作為第二個質因數，然後，由於1已經和質因數2相乘得到醜數，這時，1不需要和質因數2再做乘法操作來獲取醜數

所以，第二次操作，就是1和3、5相乘，而質因數2和第二個醜數相乘，取到最小的3作為第三個醜數，然後，由於1已經和質因數3相乘得到醜數，這時，1不需要和質因數3再做乘法操作來獲取醜數

所以，第三次操作，就是1和5相乘，而質因數2、3和第二個醜數相乘，取到最小的4作為第四個醜數，然後，由於2已經和質因數2相乘得到醜數，這時，2不需要和質因數2再做乘法操作來獲取醜數

依次類推，即可依次得到醜數序列。

圖解

圖解

演算法實現

由於需要分別標記質因數2、3、5分別和第幾個醜數進行乘法運算，所以，可以定義三個指標對應三個質因數，指向陣列中的位置。

這樣，每次判斷出，取到的值是和某個質因數反應，就可以將該質因數對應的指標向後移動一位。

程式碼實現（Java）

public int nthUglyNumber（int n） {

//定義一個數組儲存醜數序列

int［］ dp = new int［n］；

dp［0］ = 1；

int min = Integer。MAX_VALUE；

//定義三個指標，分別對應質因數2、3、5。

int i2 = 0，i3 = 0，i5 = 0；

for （int i = 1； i < n； i++） {

//取得最小值作為下一個醜數

min = Math。min（dp［i2］ * 2，Math。min（dp［i5］ * 5，dp［i3］ * 3））；

//判斷是那一個質因數參與得到醜數，將其指標向後移動一位

if（min == dp［i3］ * 3） i3++；

if（min == dp［i5］ * 5） i5++；

if（min == dp［i2］ * 2） i2++；

//將醜數存入醜數序列

dp［i］ = min；

}

return dp［n - 1］；

}