《剑指offer》— JavaScript（33）丑数

丑数

题目描述

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

思路

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

实现代码

function GetUglyNumber_Solution(index) {
    if (index === 0) return 0;
    var uglyNum = [1];
    var factor2 = 0,
        factor3 = 0,
        factor5 = 0;
    for (var i = 1; i < index; i++) {
        uglyNum[i] = Math.min(uglyNum[factor2] * 2, uglyNum[factor3] * 3, uglyNum[factor5] * 5);
        if (uglyNum[i] === uglyNum[factor2] * 2) factor2++;
        if (uglyNum[i] === uglyNum[factor3] * 3) factor3++;
        if (uglyNum[i] === uglyNum[factor5] * 5) factor5++;
    }
    return uglyNum[index - 1];
}