题目
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序 的第N个丑数。
要判断一个数是不是丑数，最简单的就是用下面这个函数进行遍历：
public bool isUglyNumber(int input){
while(input%2==0){
input/=2;
}
while(input%3==0){
input/=3;
}
while(input%5==0){
input/=5;
}
if(input == 1){
return true;
}else{
return false;
}
}
分析
假如我们用上面的方法，从1开始进行遍历，每遍历一个数就进行判断，是丑数就添加进一个丑数数组，直到满足丑数数组的长度是N。最后输出最后一个数就是结果。
但是如果N太大，就需要判断很多不是丑数的数，效率不高。
而我们知道，丑数的定义可以简单的看做一个公式2^x3^y5^.因此，一个丑数乘以2的倍数，3的倍数，5的倍数之后也是丑数，那么我们就可以从头开始，直接找到丑数并 添加到丑数数组，直到丑数数组的长度是N。
具体来说：
例如目前丑数数组中只有1
那么 21=2，21=3，5*1=5；
我们选最小的放到丑数数组侯曼，这时候，丑数数组是{1，2}。
按照这种思想，
每增加一个丑数，需要进行比较的数就增加3，这个时候有：31=3，51=5； 21=2，23=6，5*2=10；
我们依旧选最小的是3，按照这种方式，每增加一个丑数，就要增加三个新的丑数进行判断。过于暴力。
假如我们只去记录2，3，5被选取时对应的丑数的下标，下一次比较的时候，我们只去比较这三个数，选取最小的，下标前移一个单位。 这样就永远只需要比较三个数。
代码
public class Solution {
public int GetUglyNumber_Solution(int index) {
if (index < 1) {
return 0;
}
int count = 0;
int [] ugltNumbers = new int[index];
ugltNumbers[0] = 1;
// 2.3.5对应的要乘的最小数的索引
int i2 = 0;
int i3 = 0;
int i5 = 0;
while (count < index-1) {
int tempResult = min(ugltNumbers[i2] * 2, ugltNumbers[i3] * 3, ugltNumbers[i5] * 5);
if (tempResult == ugltNumbers[i2] * 2) {
i2++;
}
if (tempResult == ugltNumbers[i3] * 3) {
i3++;
}
if (tempResult == ugltNumbers[i5] * 5) {
i5++;
}
ugltNumbers[++count] = tempResult;
}
return ugltNumbers[ index - 1];
}
// 找出三个数中最小的那个
public int min(int x,int y ,int z){
if (x>y) {
x=y;
}
return x>z?z:x;
}
}
