剑指offer49. 丑数

我们把只包含质因子 2、3 和5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

思路

动态转移方程 f(i) = Math.min(temp[a] * 2, temp[b] * 3, temp[c] * 5) 在数学上的意思，丑数，肯定是之前的一个丑数✖️ （2 || 3 || 5 ）只要找到比现在大的就行

开辟数组保存每个下标的丑数。

不断更新a b c 的下标，一旦等于了向前挪一个，就会变成大于了，然后再次看这三个数的大小

解答

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function(n) {
    if(n===1) return n
    let tmp = [1]
    let a=0,b=0,c=0
    for(let i=1;i<n;i++) {
        tmp[i] = Math.min(tmp[a]*2,tmp[b]*3,tmp[c]*5)
        tmp[i] >= tmp[a] * 2 ? a++ : 0
        tmp[i] >= tmp[b] * 3 ? b++ : 0
        tmp[i] >= tmp[c] * 5 ? c++ : 0

    }
    return tmp[tmp.length - 1]
};