LintCode 4. 丑数 II JavaScript算法

描述

设计一个算法，找出只含素因子2，3，5 的第 n 小的数。

符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12…

说明

我们可以认为 1 也是一个丑数。

样例

- 样例 1：

输入：9
输出：10

- 样例 2：

输入：1
输出：1

挑战

要求时间复杂度为 O(nlogn) 或者 O(n)。

解析

这里百度了一下什么叫丑数：

说法一（ugly number）：把只包含质因子2，3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。 习惯上我们把1当做是第一个丑数。

说法二(humble number)：对于一给定的素数集合 S = {p1, p2, …, pK},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p1、p1p2、p1p1、p1p2p3…(还有其它)。该集合被称为S集合的“丑数集合”。

根据题目的解释，应该更贴近说法一。

const nthUglyNumber = function (n) {
    if(n === 0) return 0;
    let uglyNum = [1];
    let t2 = 0, t3 = 0, t5 = 0;
    for(let i=1; i<n; i++){
        uglyNum[i] = Math.min(uglyNum[t2]*2,uglyNum[t3]*3,uglyNum[t5]*5);
        if(uglyNum[i] === uglyNum[t2] * 2) t2++;
        if(uglyNum[i] === uglyNum[t3] * 3) t3++;
        if(uglyNum[i] === uglyNum[t5] * 5) t5++;
    }
    return uglyNum[n - 1];
}

运行结果