力扣專題——264.醜數 II

264.醜數 II

給你一個整數 n ，請你找出并傳回第 n 個 醜數 。

醜數 就是隻包含質因數 2、3 和/或 5 的正整數。

示例 1：

輸入：n = 10
輸出：12
解釋：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 個醜數組成的序列。
           

思路：

通過三指針寫法來解決該問題。

三個指針分别表示該位置乘以2，3，5

使用min方法取其中最小的值添加到結果數組中

然後将值相同的指針加一，這樣可以避免資料重複

整個流程也保證了最新添加的數的因數是2，3，5

源碼：

python和c

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        res=[1]
        index1=0
        index2=0
        index3=0
        for i in range(n-1):
            res.append(min(res[index1]*2,res[index2]*3,res[index3]*5))
            if(res[-1]==res[index1]*2):
                index1+=1
            if(res[-1]==res[index2]*3):
                index2+=1    
            if(res[-1]==res[index3]*5):
                index3+=1
        return res[-1]    

作者：shang-91
連結：https://leetcode-cn.com/problems/ugly-number-ii/solution/san-zhi-zhen-xie-fa-by-shang-91-0cpy/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
           

int nthUglyNumber(int n){
    int res[n+1];
    res[0]=1;
    int idx1=0,idx2=0,idx3=0;
    for(int i=1;i<n;i++){
        int no1=res[idx1]*2,no2=res[idx2]*3,no3=res[idx3]*5;
        res[i]=fmin(fmin(no1,no2),no3);
        if(res[i]==res[idx1]*2)
            idx1++;
        if(res[i]==res[idx2]*3)
            idx2++;
        if(res[i]==res[idx3]*5)
            idx3++;    
    }
    return res[n-1];
}