參考資料文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-617884.html
劍指 Offer 49. 丑數(shù)
我們把只包含質(zhì)因子 2、3 和 5 的數(shù)稱(chēng)作丑數(shù)（Ugly Number）。求按從小到大的順序的第 n 個(gè)丑數(shù)。
示例:
輸入: n = 10
輸出: 12
解釋: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個(gè)丑數(shù)。
說(shuō)明:
1 是丑數(shù)。
n 不超過(guò)1690。
注意到丑數(shù)只包含質(zhì)因子是2，3，5。所以，丑數(shù)必然是有這三個(gè)數(shù)若干次相乘得到。而丑數(shù)序列保持從小到大，所以當(dāng)前的丑數(shù)必然是前面某個(gè)丑數(shù)乘2或者3或者5得到的。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-617884.html
class Solution {
// 自己寫(xiě)的暴力法，通過(guò)了500個(gè)測(cè)試用例，最后到n等于一萬(wàn)多時(shí)還是超時(shí)了
public int nthUglyNumber1(int n) {
int i=0;
while(n>0){
i++;
if(isUgly(i)){
n--;
}
}
return i;
}
public boolean isUgly(int num){
while(num%2==0){
num/=2;
}
while(num%3==0){
num/=3;
}
while(num%5==0){
num/=5;
}
return num==1;
}
// 參考力扣K神寫(xiě)的,
//主要思想是所有丑數(shù)都是2，3，5這三個(gè)數(shù)的乘積；
// 而當(dāng)前的丑數(shù)是“上一個(gè)”丑數(shù)乘上2或者3或者5之后的結(jié)果，
//注意維持大小順序(see Math.min(Math.min(n2,n3),n5);)。
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0]=1;
int a=0,b=0,c=0;
for(int i=1;i<n;i++ ){
int n2=dp[a]*2,n3=dp[b]*3,n5=dp[c]*5;
dp[i]=Math.min(Math.min(n2,n3),n5);
if(dp[i]==n2) a++;
if(dp[i]==n3) b++;
if(dp[i]==n5) c++;
}
return dp[n-1];
}
}
到了這里，關(guān)于劍指 Offer 49. !!丑數(shù) (找數(shù)學(xué)規(guī)律)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
