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

我开始想的是想的是通过除法，然后逐个判断方式。比如判断一个丑数，由题意知，只包含2、3、5。对于14的判断规则就是先拿掉所有的2的因子，再拿掉所有3的因子，最后拿到5的因子，最后为1，则说明是丑数。

思路1：

哈哈，一个时间复杂度比较高的算法，在牛客上没跑成功。我自己验证的时候感觉没问题

public class ac {
    public static void main(String[] args) {
        System.out.print(GetUglyNumber_Solution(1));
    }    
    public static int GetUglyNumber_Solution(int index) {
            if(index<0)
                return 0;
            int num = 0;
            int cur = 0;
            while(cur < index){
                num++;//+1用来下一个数的判断
                if(isUgly(num))
                    cur++;//维持已知的丑数数量

            }
            return num;
        }        
    public static boolean isUgly(int num){
            while(num%2 == 0)//能被2整除就除以一个2，消除所有2的因子
                num = num/2;
            while(num%3 == 0)//能被3整除就除以一个3，消除所有3的因子
                num = num/3;
            while(num%5 == 0)//能被5整除就除以一个5，消除所有5的因子
                num = num/5;//如果是丑数，去掉这些因子，最后只剩1了
            return (num == 1)?true:false;
        }
}

思路2：改进

得换一个大方向去思考了，用空间换时间。在使用不同的工具以及思路时，都会出现不同的写法。比如书上的方法是用一个大数组来存放这些数据，而其他题解以及讨论中，出现了是三个数组或者指针的方法。
  介绍某一种思路：将丑数存起来，然后利用丑数去计算下一个丑数数。
  过程如下：用3个数记录（指针角色），初始都指向的1。也就是第一个丑数。然后三个指针指向的数分别乘上因子2，3，5，然后进行比较。

  • 初始集合为{1}-> 比较1*2，1*3，1*5 最小值2。需要更新第1个指针，此时指向2（指针++）
  • {1,2} -> 比较2*2，1*3，1*5 最小值3。需要更新第2个指针，让他指向2（指针++）
  • {1，2，3} -> 比较2*2，2*3，1*5 最小值4。需要更新第1个指针，让他指向3（指针++）
  • {1，2，3，4} -> 比较3*2，2*3，1*5 最小值5。需要更新第3个指针，指向2（指针++）
  • {1，2，3，4，5} ->比较3*2，2*3，2*5 最小值6。需要同时更新第1和第2指针，均++
    则第1指针指向4，第2指针指向3
  • {1,2,3,4,5,6} 比较4*2，3*3，2*5 最小值8 更新第1指针，指向5
  • {1,2,3,4,5,6,8} 比较5*2，3*3，2*5 最小值9 更新第2指针 指向4

  除了在6的地方出现了相等，处理方式稍微不一样，其余的都相同。谁乘出来是最小的，最小的加入到集合后，然后就把谁的位置往后挪一个。
  这个方法的原理是，已经有了一部分丑数，且当前拥有的丑数最大值为M，需要找到比M大，又最接近M的丑数。下一个抽数一定是之前的某个丑数乘2，或者乘3，或者乘5的结果。以乘2为例，理当应该将所有的丑数都乘2，这样可以获得若干小于M和大于M的丑数，小于M的丑数已经在我们的集合中了，所以我们需要在大于M的这些数中找到最小值，也就是最接近M的丑数，记录其为n2。同理，在所有丑数乘3的时候，也能找到一个最接近M的丑数，记录为n3，同理有一个n5。所以，我们需要比较n2,n3,n5的最小值。
  而使用i2,i3,i5的意义是，当前所指向的丑数，乘上对应的因子，就是最接近当前集合中，比M大又最接近M的丑数。比如上面分析的{1,2,3,4,5,6} i2指向4，i3指向3，i5指向2。i2指向4，表明当前序列中，乘2比M=6还大，又最接近的数就是4了。同理，i3表示，如果你要通过乘上3，获取要比M大的数，还接近M，那就是3了。因此，正确的维护i2、i3、i5可以将刚刚叙述的所有数都乘2、3、5，并判断这一过程省略。（如果看起来还觉得绕，其实就是因为这个本身就是一个优化版，正常来说，应当维持3个队列（乘2乘3乘5），每个队列中都记录比M大或者小的数，而通过一个while循环判断，获取这个队列中的比M大一丢丢的数是可以做到的，然后在将获取的三个数比较）
  那么，如何正确的维护i2/i3/i5呢，试想，如果当前的某个丑数是通过乘2获取的，比如获取了3乘2，为6，所以把6装入到集合中，那么显然i2所指向的3再乘2就等于当前最大丑数，那么i2指向下一个丑数时，不管下一个丑数是多少，乘上2一定会比6大了，并且还是当前所有丑数中，乘2最逼近于6的。

import java.util.ArrayList;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index<=0)
            return 0;
        ArrayList<Integer> list = new ArrayList<Integer>();
        //add进第一个丑数1
        list.add(1);
        //三个下标用于记录丑数的位置
        int i2=0,i3=0,i5=0;
        while(list.size()<index){
            //三个数都是可能的丑数，取最小的放进丑数数组里面
            int n2=list.get(i2)*2;
            int n3=list.get(i3)*3;
            int n5=list.get(i5)*5;
            int min = Math.min(n2,Math.min(n3,n5));
            list.add(min);
            if(min==n2)
                i2++;
            if(min==n3)
                i3++;
            if(min==n5)
                i5++;
        }
        return list.get(list.size()-1);
    }
}
/* 三个数求最小 上面调用的是API
public int Min(int a,int b,int c) {
        int min=a;
        if(min>b)
            min=b;
        if(min>c)
            min=c;
        return min;
      }*/