编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
image.png
分析：除了第一个丑数1以外 每一个丑数都是 由 2，3，5，
乘以原有的丑数集合{1。。。。}，来扩充，
注意一点，在该题目中每次扩充一位即可，
每次都要比较，（2，3，5）所乘得到的数，
选择最小的数
（，加入丑数集合中，此时，将刚刚被乘以的那个（
2，3，5）去乘以，集合中的下一个数
（可能会相等，此时那相等的数，同时乘以集合的下一个）。
（2，3，5）每个都数都要乘以丑数数组中的每一个数，
设每个（2，3，5）都有一个指针（都在遍历丑数数组），
当乘以丑数数组的积为最小时
（若相等，指针都会指向下一个），
指针指向下一个，依次类推。
*/
class Solution {
public int nthUglyNumber(int n) {
int [] res = new int[n];
res[0] = 1;
int i2 = 0, i3 = 0, i5 = 0,k = 0;
for( k = 1;k<n;k++) {
int m2 = res[i2] * 2, m3 = res[i3] * 3, m5 = res[i5] * 5;
int mn = Math.min(m2, Math.min(m3, m5));
if (mn == m2) ++i2;
if (mn == m3) ++i3;
if (mn == m5) ++i5;
res[k] = mn;
}
return res[k-1];
}
}
