题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
解题思路（抄题 -.-|||）
根据丑数的定义，一个丑数应该是另外一个丑数乘以2,3,5的结果（1除外，乘1还是自身）。
我们创建一个数组，确保里面的丑数是从小到大排好序的，每个丑数都是有前面的丑数乘以2或3或5得到。
假设我们已有的最大丑数为M，那么M的下一个丑数肯定是由前面的某一个丑数乘以2 或者 乘以3 或者 乘以5得到
以乘以2为例，如果将前M个丑数都乘以2 ，那么必然能得到 一部分丑数 是小于M （前M个里面），以及一部分大于等于M的丑数，类似的，前M个丑数乘以3 或者 5 都能得到类似的结果，而我们只关心M的下一个丑数，也就是说再大于M的丑数里面 我们找那个最小的。
这也是为什么确保数组有序，这样我们乘2得到的结果也是有序的，乘3得到的也是有序的 ....
事实上并不需要每个小于M的丑数都乘以2，肯定存在某一个丑数（前M个里面的）T2，比他小的乘以2都小于M，比他大的乘以2 都会太大。
而 T2*2 可能正好 大于等于M，类似的 也有T3 T5，我们需要找到的是
min(T2*2,T3*3,T5*5) 得到的就是 恰好M的下一个丑数。
题解
public int GetUglyNumber_Solution(int index) {
if (index <= 0) return 0;
int mem[] = new int[index];
mem[0] = 1;
int t2=0,t3=0,t5=0;
for (int i = 1; i < index; i++) {
mem[i] = min(t2*2,t3*3,t5*5);
if (t2*2 == mem[i]) t2++;
if (t3*3 == mem[i]) t3++;
if (t5*5 == mem[i]) t5++;
}
return mem[index-1];
}
public int min(int a,int b,int c){
int min = a;
if (b < min ){
min = b;
}
if (c < min){
min = c;
}
return min;
}
