题解 | #丑数#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param index int整型 
 * @return int整型
 */
function GetUglyNumber_Solution( index ) {
    if(index <= 0) return 0;
    // 动态规划法
    // dp[n]表示第n个丑数的值为dp[n]
    // 丑数 = Math.min（已有丑数 * 质因数（2 3 5））
    const dp = [];
    dp[1] = 1;
    // 定义三个指针分别表示乘2、乘3、乘5的已有丑数下标
    let i2 = 1;
    let i3 = 1;
    let i5 = 1;
    for(let i = 2; i <= index; i++){
        let min = Math.min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5);
        // 如果当前丑数是由有序丑数序列dp中某个丑数*2得到的，则i2指针要加1，因为这个丑数已经加入序列了，以后不需要再参与比较
        if(min === dp[i2] * 2) i2++;
        if(min === dp[i3] * 3) i3++;
        if(min === dp[i5] * 5) i5++;
        dp[i] = min;
    }
    return dp[index];
}
module.exports = {
    GetUglyNumber_Solution : GetUglyNumber_Solution
};