丑数
题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
思路
- 按顺序将丑数保存在数组中，然后求下一个丑数；
- 下一个丑数是由数组中某个丑数A * 2，B * 3，C * 5中的最小值得来的。
- 按照题目规定，第一个丑数是1，存入数组中；
- 第二个丑数为1*2，1*3，1*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];
}
