题目链接：

 

题意：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

 

题解：这题最开始是暴力做的。就是根据定义，依次做判断。然后TLE了。emmm...然后就有了接下来的解法。

因为这个number只包含2,3,5的因子，所以根据以2，3，5来做判断和维护。令number数组里的第一个元素为1。因为我们要让丑数数列有序，所以要每次使这三个因子组成的最小的数进入数组。

ugly:1

array 2: 2

array 3: 3

array 5: 5

比较（2，3，5）->min_n = 2,2进入ugly[]

 

 

ugly:1 2

array 2: 4

array 3: 3 6

array 5: 5 10

然后比较当前的值(4，3，5)，3再进入ugly[]

怎么保证每次都是比较最前面的数呢。我们用做标记的方式实现。

i2,i3,i5来表示当前的位置。如果当前的number能除尽它们，指针就向后移。

 

代码：

1 public class Solution { 2     public int GetUglyNumber_Solution(int index) { 3         if(index <= 0){ 4             return 0; 5         } 6         int []ugly = new int[index]; 7         int i2=0; 8         int i3=0; 9         int i5=0;10         int cnt = 0;11         ugly[0] = 1;12         int num = 0;13         while(cnt < index-1){14             num = Math.min(ugly[i2]*2,Math.min(ugly[i3]*3,ugly[i5]*5));15             if(num == ugly[i2] * 2)    i2++;16             if(num == ugly[i3] * 3)    i3++;17             if(num == ugly[i5] * 5)    i5++;18             ugly[++cnt] = num;19             20         }21         return ugly[index-1];22     }23 }