把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
题目解答
我们可以维护三个队列：
（1）丑数数组： 1
乘以2的队列：2
乘以3的队列：3
乘以5的队列：5
选择三个队列头最小的数2加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
（2）丑数数组：1,2
选择三个队列头最小的数3加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
选择三个队列头里最小的数4加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
选择三个队列头里最小的数5加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
选择三个队列头里最小的数6加入丑数数组，但我们发现，有两个队列头都为6，所以我们弹出两个队列头，同时将12,18,30放入三个队列；
我们没有必要维护三个队列，只需要记录三个指针显示到达哪一步；“|”表示指针,arr表示丑数数组；
目前指针指向0,0,0，队列头arr[0] * 2 = 2, arr[0] * 3 = 3, arr[0] * 5 = 5
目前指针指向1,0,0，队列头arr[1] * 2 = 4, arr[0] * 3 = 3, arr[0] * 5 = 5
目前指针指向1,1,0，队列头arr[1] * 2 = 4, arr[1] * 3 = 6, arr[0] * 5 = 5
import java.util.ArrayList;
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index<7){
return index;
}
int p2=0,p3=0,p5=0,newNum=1;
ArrayList<Integer> list=new ArrayList<>();
list.add(newNum);
while(list.size()<index){
int m2=list.get(p2)*2;
int m3=list.get(p3)*3;
int m5=list.get(p5)*5;
newNum=Math.min(m2,Math.min(m3,m5));
list.add(newNum);
if(newNum==m2) p2++;
if(newNum==m3) p3++;
if(newNum==m5) p5++;
}
return newNum;
}
}
java新建可变长度的数组用ArrayList
