【剑指offer】丑数

题目链接：丑数

题意：把只包含质因子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 }