33-丑数

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

分析

按顺序将丑数保存在数组中，然后求下一个丑数；
下一个丑数是由数组中某个丑数A * 2，B * 3，C * 5中的最小值得来的。
按照题目规定，第一个丑数是1，存入数组中；
第二个丑数为12，13，15三个中的最小值；
第三个丑数为22，13，15三个中的最小值，依次类推，求出第N个数组。

代码

function GetUglyNumber_Solution(index)
{
    // write code here
    if(index===0) return 0;
    let arr = [1];
    let f1 = 0;
    let f2 = 0;
    let f3 = 0;
    for(let i=1;i<index;i++){
        arr[i] = Math.min(arr[f1]*2,arr[f2]*3,arr[f3]*5);
        if(arr[i]===arr[f1]*2) f1++;
        if(arr[i]===arr[f2]*3) f2++;
        if(arr[i]===arr[f3]*5) f3++;
    }
    return arr[index-1];
}