題目來(lái)源
- 來(lái)源：力扣264
題目描述
描述：
? 編寫(xiě)一個(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ù)刁卜。
說(shuō)明:? 1 是丑數(shù)志电。
? n 不超過(guò)1690。
解法分析
- 題目要求：第k個(gè)丑數(shù)蛔趴。所以我們需要求丑數(shù)的升序序列的獲取方式挑辆。
首先，分析丑數(shù)的獲取方式
- 由第一個(gè)丑數(shù)1孝情，分別于三個(gè)質(zhì)因數(shù)相乘之拨，得到三個(gè)丑數(shù)，然后排序咧叭，得到1、2烁竭、3菲茬、5.
- 然后對(duì)第二個(gè)丑數(shù)2，再次進(jìn)行一步驟的操作派撕，得到丑數(shù)4婉弹、6、10.升序排列得到1终吼、2镀赌、3、4际跪、5商佛、6、10.
- 再對(duì)第三個(gè)丑數(shù)進(jìn)行一步驟的操作姆打，再對(duì)整體的數(shù)列進(jìn)行排序良姆，即可得到新的丑數(shù)序列。
- 丑數(shù)既然可以通過(guò)這種方式獲得幔戏，針對(duì)題目要求玛追，可以進(jìn)行一些修改，即可得到第k個(gè)丑數(shù)闲延。
實(shí)現(xiàn)方式思路如下痊剖，這里舉個(gè)例子
- 對(duì)于第一個(gè)質(zhì)因數(shù)，分別和2垒玲、3陆馁、5相乘，取到最小的2侍匙，作為第二個(gè)質(zhì)因數(shù)氮惯，然后叮雳，由于1已經(jīng)和質(zhì)因數(shù)2相乘得到丑數(shù)，這時(shí)妇汗，1不需要和質(zhì)因數(shù)2再做乘法操作來(lái)獲取丑數(shù)
- 所以帘不，第二次操作，就是1和3杨箭、5相乘寞焙，而質(zhì)因數(shù)2和第二個(gè)丑數(shù)相乘，取到最小的3作為第三個(gè)丑數(shù)互婿，然后捣郊，由于1已經(jīng)和質(zhì)因數(shù)3相乘得到丑數(shù)，這時(shí)慈参，1不需要和質(zhì)因數(shù)3再做乘法操作來(lái)獲取丑數(shù)
- 所以呛牲，第三次操作，就是1和5相乘驮配，而質(zhì)因數(shù)2娘扩、3和第二個(gè)丑數(shù)相乘，取到最小的4作為第四個(gè)丑數(shù)壮锻，然后琐旁，由于2已經(jīng)和質(zhì)因數(shù)2相乘得到丑數(shù)，這時(shí)猜绣，2不需要和質(zhì)因數(shù)2再做乘法操作來(lái)獲取丑數(shù)
- 依次類推灰殴，即可依次得到丑數(shù)序列。
圖解
丑數(shù).png
算法實(shí)現(xiàn)
- 由于需要分別標(biāo)記質(zhì)因數(shù)2掰邢、3牺陶、5分別和第幾個(gè)丑數(shù)進(jìn)行乘法運(yùn)算，所以辣之，可以定義三個(gè)指針對(duì)應(yīng)三個(gè)質(zhì)因數(shù)义图，指向數(shù)組中的位置。
- 這樣召烂，每次判斷出碱工，取到的值是和某個(gè)質(zhì)因數(shù)反應(yīng)，就可以將該質(zhì)因數(shù)對(duì)應(yīng)的指針向后移動(dòng)一位奏夫。
代碼實(shí)現(xiàn)（Java）
public int nthUglyNumber(int n) {
//定義一個(gè)數(shù)組存儲(chǔ)丑數(shù)序列
int[] dp = new int[n];
dp[0] = 1;
int min = Integer.MAX_VALUE;
//定義三個(gè)指針怕篷，分別對(duì)應(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ù)廊谓，將其指針向后移動(dòng)一位
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];
}
