1. 题目描述
把只包含因子 2、3 和 5 的数称作丑数(Ugly Number)。例如 6、8 都是丑数,但 14 不是,因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 1500 个丑数。
2. 解题思路
2.1 思路一
根据定义,将给定的数不断除 2、3、5,看看能不能除尽即可。然后从 1 遍历到 1500。
2.2 思路二
前面速度慢是因为计算了太多非丑数。根据丑数定义,每一个丑数都是根据前面一个丑数乘以 2、3 或者 5 得到的。
在确保顺序的情况下,逐步计算即可。
3. 代码
3.1 思路一实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| function isUgly(number) { while (number % 2 === 0) { number /= 2 } while (number % 3 === 0) { number /= 3 } while (number % 5 === 0) { number /= 5 } return number === 1 }
function getUglyNumber(index) { if (index <= 0) return 0
let number = 0, uglyFound = 0
while (uglyFound < index) { ++number if (isUgly(number)) { ++uglyFound } }
return number }
|
3.2 思路二实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| function getUglyNumber(index) { if (index <= 0) return 0
const uglyNum = [1] let pointer2 = 0, pointer3 = 0, pointer5 = 0
for (let i = 1; i < index; ++i) { uglyNum[i] = Math.min(uglyNum[pointer2] * 2, uglyNum[pointer3] * 3, uglyNum[pointer5] * 5) if (uglyNum[i] == uglyNum[pointer2] * 2) ++pointer2 if (uglyNum[i] == uglyNum[pointer3] * 3) ++pointer3 if (uglyNum[i] == uglyNum[pointer5] * 5) ++pointer5 }
return uglyNum[index - 1] }
console.log(getUglyNumber(1500))
|