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
}

// 找出 [1, index) 之中的所有丑数
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] // 存放丑数
// 2,3,5 三个因子各自的指针
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)) // 859963392