??前面的話??

大家好！本篇文章將介紹力扣[劍指offer]題解，展示代碼語言暫時為：C與Java，（后續會更新C++代碼）

📒博客主頁：未見花聞的博客主頁
🎉歡迎關注🔎點贊👍收藏??留言📝
📌本文由未見花聞原創，CSDN首發！
📆首發時間：🌴2021年10月28日🌴
??堅持和努力一定能換來詩與遠方！
💭刷題推薦書籍：📚《劍指offer第1版》，📚《劍指offer第2版》
💬參考在線編程網站：🌐牛客網🌐力扣
🙏作者水平很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！
博主的碼云gitee，平常博主寫的程式代碼都在里面，

??劍指 Offer 49. 丑數??

🔐題目詳情

我們把只包含質因子 2、3 和 5 的數稱作丑數（Ugly Number），求按從小到大的順序的第 n 個丑數，

示例：

輸入: n = 10
輸出: 12
解釋: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個丑數，

提示：

1. 1 是丑數，
2. n 不超過1690，

💡解題思路

該題定義了丑數首項為1，并且只包含質因子 2、3 和 5（除了1以外，只能被2,3,5整除）
那么丑數一定是前面丑數某一項乘以質因子的數集中的最小值，因為有三個質因子，所以該數集有三個元素，
不妨設所求丑數 u g l y [ n ] ugly[n] ugly[n]的項數為 n n n，數集中三個數分別為 n a ， n b ， n c na，nb，nc na，nb，nc，分別對應丑數第 a ， b ， c a，b，c a，b，c項，其中 a , b , c < n a,b,c<n a,b,c<n，
則：
u g l y [ n ] = m i n { n a , n b , n c } ugly[n] = min\{na, nb, nc\} ugly[n]=min{na,nb,nc}
{ n a = u g l y [ a ] ? 2 n b = u g l y [ b ] ? 3 n c = u g l y [ c ] ? 5 , a , b , c < n \left\{ \begin{array}{c} na = ugly[a] ? 2 \\ nb = ugly[b] ? 3 \\ nc = ugly[c] ? 5 \end{array} \right. ,a,b,c < n ????na=ugly[a]?2nb=ugly[b]?3nc=ugly[c]?5?,a,b,c<n

取得數集中最小值后，使最小值對應的項數加1，比如na最小，則a++，如果存在多個最小值，每個最小值對應的項數都需要加1，,最后按照同樣的方式求丑數下一項，

🔑源代碼

C語言：

int min(int x, int y, int z)
{
    int m = 0;
    m = x < y ? x : y;
    m = m < z ? m : z;
    return m;
}
int nthUglyNumber(int n){
    int a = 0;
    int b = 0;
    int c = 0;
    int* ugly = (int*)malloc(sizeof(int) * n);
    int i = 0;
    ugly[0] = 1;
    for (i = 1; i < n; i++) 
    {
        int na = ugly[a] * 2;
        int nb = ugly[b] * 3;
        int nc = ugly[c] * 5;
        ugly[i] = min(na, nb, nc);
        if (ugly[i] == na)
            a++;
        if (ugly[i] == nb)
            b++;
        if (ugly[i] == nc)
            c++;
    }
    return ugly[n - 1];
}

Java語言：

class Solution {
    public int nthUglyNumber(int n) {
        int a = 0;
        int b = 0;
        int c = 0;
        int[] ugly = new int[n];
        int i = 0;
        ugly[0] = 1;
        for (i = 1; i < n; i++) {
            int na = ugly[a] * 2;
            int nb = ugly[b] * 3;
            int nc = ugly[c] * 5;

            int min = Math.min(na, nb);
            ugly[i] = Math.min(min, nc);

            if (ugly[i] == na) a++;
            if (ugly[i] == nb) b++;
            if (ugly[i] == nc) c++;
        }
        return ugly[n - 1];
    }
}

🌱總結

對于丑數或類似丑數的問題，最重要的是想出其遞推公式，該題是依據丑數的后一項一定在前面某項乘以質因子所得的數集中，其最小值即是這一項，