丑數(shù)
題目描述
把只包含質(zhì)因子2壶冒、3和5的數(shù)稱作丑數(shù)（Ugly Number）缕题。例如6、8都是丑數(shù)胖腾，但14不是烟零，因?yàn)樗蜃?。 習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)咸作。求按從小到大的順序的第N個(gè)丑數(shù)锨阿。
思路
- 按順序?qū)⒊髷?shù)保存在數(shù)組中，然后求下一個(gè)丑數(shù)记罚；
- 下一個(gè)丑數(shù)是由數(shù)組中某個(gè)丑數(shù)A * 2墅诡，B * 3，C * 5中的最小值得來(lái)的桐智。
- 按照題目規(guī)定末早，第一個(gè)丑數(shù)是1，存入數(shù)組中说庭；
- 第二個(gè)丑數(shù)為1*2然磷，1*3，1*5三個(gè)中的最小值口渔；
- 第三個(gè)丑數(shù)為2*2，1*3穿撮，1*5三個(gè)中的最小值缺脉，依次類推，求出第N個(gè)數(shù)組悦穿。
實(shí)現(xià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];
}
