题目

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

方法

参考：https://blog.csdn.net/qq_40816360/article/details/95313173

思路

丑数的定义是只含有质因子2、3和5。所以丑数，可以表示成 2^n * 3^m * 5^k，所以我们需要从小到大找出第N个丑数。相当于，我们需要使用2、3、5三个数互相承继，算出足够多的丑数，对丑数排序，取第N个。
换言之，其实我们可以在计算丑数的过程中，顺便排序。第一个丑数是1，用1乘以2、3、5，得到2、3、5，2是最小的，所以2是第二个丑数。2还可以乘以2、3、5得到，4，6，10。第三个丑数明显是3，3还可以乘以2、3、5得到6，9，15，那么接下来如何判断下一个丑数。
将待定丑数用乘积队列表示，目的是找到待定丑数中最小的那个
第一个丑数：1
× 2队列：2
× 3队列：3
× 5队列：5

第二个丑数：2 —— 2被拿走
丑数队列：1，2 —— 乘积队列新增数据排在后面
× 2队列：4
× 3队列：3，6
× 5队列：5，9

第三个丑数：3 —— 3被拿走
丑数队列：1，2，3
× 2队列：4，6
× 3队列：6，9
× 5队列：5，9，15

以此类推，我们只要在3个乘积队列中，比较队首，取最小的数作为下一个丑数即可

第四个丑数：4
丑数队列：1，2，3，4
× 2队列：6，8
× 3队列：6，9，12，
× 5队列：5，9，15，20

第五个丑数：5
丑数队列：1，2，3，4，5
× 2队列：6，8，10
× 3队列：6，9，12，15
× 5队列：9，15，20，25

下一个丑数是6，在×2和×3的队列都出现了，那么就同时取走
第六个丑数：5
丑数队列：1，2，3，4，6
× 2队列：8，12
× 3队列：9，12，18
× 5队列：5，9，15，20，30

以此类推，计算到第N个丑数，即可

代码

function GetUglyNumber_Solution (index) {
  // write code here
  if (index === 0) return 0
  let mul2queue = []
  let mul3queue = []
  let mul5queue = []
  let ugly
  for (let i = 0; i < index; i++) {
    let item = i === 0 ? 1 : Math.min(mul2queue[0], mul3queue[0], mul5queue[0])
    ugly = item
    if (mul2queue[0] === item) mul2queue.shift()
    if (mul3queue[0] === item) mul3queue.shift()
    if (mul5queue[0] === item) mul5queue.shift()
    mul2queue.push(item * 2)
    mul3queue.push(item * 3)
    mul5queue.push(item * 5)
  }
  return ugly
}