描述
如果一个数只有质数因子2，3，5 ，那么这个数是一个丑数。
前10个丑数分别为 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...设计一个算法，找出第N个丑数。
我们可以认为 1 也是一个丑数。
1≤n≤105
样例 1：
输入：
n = 9
输出：
10
解释：
[1,2,3,4,5,6,8,9,10,…]，第9个丑数为10。
样例 2：
输入：
n = 1
输出：
1
挑战
要求时间复杂度为 O(nlogn) 或者 O(n)。
题解
思路
结论：当前丑数必定是之前某个丑数 的 2倍、3倍、或者 5倍。
定义一个数组result存放丑数，默认第一个丑数是1。那么当前丑数一定是result数组中在他之前的丑数的2，3，5倍中最小的一个,当然这个值一定是大于result[length-1]的最小值。
result[1]=min(2result[0-length-1],3result[0-length-1],5*[0-length-1])
分别用2,3,5乘1寻找第二个丑数，得到最小值2作为第二个丑数即num[1]=2。
第三个丑数：
大于2且在21 31 51 22 32 52中的最小是==》3
4.以此类推找到第n个最小值为第n个丑数。
代码
const nthUglyNumber = function (n) { var result = [1]; var i, t, nextchoushu; while (result.length < n) { // 当前已经计算出来的丑数的最后一个 t = result[result.length - 1]; // 最后一个丑数*2 nextchoushu = t * 2; // 遍历已经计算出来的丑数 for (i = 0; i < result.length; i++) { // if (result[i] * 2 > t) { nextchoushu = Math.min(result[i] * 2, nextchoushu); } } for (i = 0; i < result.length; i++) { if (result[i] * 3 > t) { nextchoushu = Math.min(result[i] * 3, nextchoushu); } } for (i = 0; i < result.length; i++) { if (result[i] * 5 > t) { nextchoushu = Math.min(result[i] * 5, nextchoushu); } } result.push(nextchoushu); } return result[n - 1]; }
