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