題目描述
設(shè)計(jì)一個(gè)算法，找出只含素因子2厚骗，3，5 的第 n 大的數(shù)兢哭。1也是一個(gè)丑數(shù)领舰。
思路
方法一
每個(gè)丑數(shù)都是2..3..5..的結(jié)果
創(chuàng)建保存丑數(shù)的數(shù)組a，設(shè)a[0]=1
用index2，index3提揍，index5表示丑數(shù)分解包含了2啤月、3、5的個(gè)數(shù)劳跃，初始化為0
每次求min(a[indexk]k)谎仲，得到當(dāng)前最小的丑數(shù)，寫(xiě)入數(shù)組刨仑，并將indexk++
這樣做即可保證a數(shù)組中能保存所有的按序排列的丑數(shù)郑诺，輸出第a[n-1]個(gè)元素即可。方法二
將1加入保存丑數(shù)的數(shù)組a杉武，將2,3,5加入優(yōu)先隊(duì)列pq
每次從pq取min辙诞，如果min與a[tmp]不等，數(shù)組保存min轻抱，并將min*2,3,5的值加入優(yōu)先隊(duì)列飞涂。如果相等，跳過(guò)祈搜。
這樣做较店，最終可以得到a[n-1]個(gè)元素即為結(jié)果
代碼
int nthUglyNumber(int n) {
// Write your code here
int index2 = 0;
int index3 = 0;
int index5 = 0;
int[] res = new int[n];
res[0] = 1;
int count = 1;
while(count < n){
res[count] = min(res[index2]*2, res[index3]*3, res[index5]*5);
if(res[count] == res[index2]*2) index2++;
if(res[count] == res[index3]*3) index3++;
if(res[count] == res[index5]*5) index5++;
count++;
}
return res[--count];
}
private int min(int a1, int a2, int a3){
if(a1 < a2){
if(a1 < a3)
return a1;
else
return a3;
}else if(a2 < a3){
return a2;
}else{
return a3;
}
}
考差點(diǎn)
- 優(yōu)先隊(duì)列
- 數(shù)組下標(biāo)的靈活運(yùn)用
