264. 丑数 II - 每日一题

难度：中等

给你一个整数 n ，请你找出并返回第 n 个丑数。

丑数就是只包含质因数 2 、 3 和 / 或 5 的正整数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

提示：

丑数的判断方式

三指针法：因为丑数只是因数只有 2,3,5 的数；

所以先设置一个 $dp$ 数组表示当前已经找出并排列好的丑数数组；

再 3 个指针： $i,j,k$ 表示将当前已经排好的数组元素 $*2，*3，*5$ 所得的数组（实际上，因为所得的数字最终会加入唯一的排序数组，所以并不用真正将 3 个数组建立起来），

因为排序后数组 $*2，*3，*5$ 得到的也是已经排序数组，接下来的目的就是从这 3 个虚拟数组中的头元素中取得最小那个值；（实际上并不会出现 3 个数组）

所以关键就是如何用这 3 个指针进行选择，

实际上排序并不是在加入排序数组后才整理排序，而是每次用老元素 $*2，*3，*5$ 生成新元素的时候，选择最小的加入达到排序目的，这个时候指针移动就起到作用了，如下过程所示：

-----------------------------------------------------

已经排好的数组，先放进第一个丑数 $1:[1]$

排好数组 $*2 ：[1]*2=2$

排好数组 $*3 ：[1]*3=3$

排好数组 $*5 ：[1]*5=5$

选结果中最小的数加入数组，此时明显是 2，新的排序数组为 [1,2]；

-----------------------------------------------------

已经排好的数组:[1，2]------ 此时上次结果中，2，3，5 只用到了 2；但 3 明显是这次需要加入的数；既然 2 已经加入，再去对比 2 没意义了，那么就将（2 的指针） [1] 转向下一位 [2]，对比（下一个元素 2 和 3，5）的大小，取最小的加入；

排好数组 $*2 ：[2]*2=4$

排好数组 $*3 ：[1]*3=3$

排好数组 $*5 ：[1]*5=5$

选结果中最小的数加入数组，此时明显是 3，新的排序数组为 [1,2,3]；

依次类推；可以看到，实际上，只需将指针进行分别移动就可以了；所以要做出 3 个指针；

-----------------------------------------------------

维护 3 个值 $n2,n3,n5$ ,，表示将当前 2,3,5 对应的指针。

将 $Math.min(2*res[n2],3*res[n3],5*res[n5])$ 加入 res 中

因为可能 3 组数出现重复，所以加入时需要去重

	var nthUglyNumber = function(n) {
	let res=[1];
	let n2=0,n3=0,n5=0;
	let i=0;
	while(res.length<n){
	let val=Math.min(2res[n2],3res[n3],5*res[n5]);
	if(res[n2]*2==val){
	n2+=1;
	}else if(res[n3]*3==val){
	n3+=1;
	}else{
	n5+=1;
	}
	if(res[res.length-1]!=val){
	res.push(val);
	}
	}
	return res[n-1];
	};