题解 | #丑数#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param index int整型 
 * @return int整型
 */
function GetUglyNumber_Solution( index ) {
    // 动态规划
    // dp[i]代表第i个丑数为dp[i]
    // 丑数肯定是由已知丑数乘2、3或5得来的
    // 定义三个指针 i2、i3 和 i5,分别指向当前已有的丑数序列中可以乘以 2、3 和 5 生成下一个丑数的索引位置。（即标注已有丑数序列中还没有乘过2、3或5的索引位置）
    // 假设已知前n-1个丑数，求第n个丑数，那么三个指针i2、i3 和 i5,分别指向三个分别乘以2,3,5大于第n-1个丑数的丑数，求得三个乘积的最小值即为第n个丑数。
    // 丑数 = Math.min（某三个已有丑数 * 质因数（2 3 5））
    if(index <= 0) return 0;
    const dp = [];
    dp[1] = 1;
    let i2 = 1;
    let i3 = 1;
    let i5 = 1;
    for(let i = 2; i <= index; i++){
        dp[i] = Math.min(dp[i2]*2, dp[i3]*3, dp[i5]*5);
        if(dp[i] === dp[i2]*2) i2++;
        if(dp[i] === dp[i3]*3) i3++;
        if(dp[i] === dp[i5]*5) i5++;
    }
    return dp[index];
}
module.exports = {
    GetUglyNumber_Solution : GetUglyNumber_Solution
};