求第N个丑数（java实现）

题目：https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b?tpId=13&tqId=11186&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

方法一：
暴力法：从1开始判断当前数是否为丑数，是则i++，直到i=N则输出对应的数即可。
如何判断当前数是否为丑数？
答：一直整除2直到除不尽，再一直整除3直到除不尽，再一直整除5直到除不尽，看最后得到的数是否为1？代码实现是 三个while循环： while（n%2 == 0） n=n/2；…

方法二：最初的思路是将丑数算出来，因为后面的丑数都是前面丑数*2,*3,*5得到的，但苦于不知道拿哪几个数进行比较取最小值，所以没能实现。看了别人的思路后，记录下来：
核心是用三个索引，标记当前的临界位置。难点是数组中的元素一直在变多。

每循环一次最多改变四个量，最少改变两个量
先建立长度为N的数组uglyNum，以便存储求来的丑数。按照程序的顺序来求，
初始值uglyNum[0] = 1;三路索引初始均指向第一个数。三个索引相互独立
第一次比较：
1*2
1*3 三个中的最小值为2，所以下一个丑数取2，那么数组中的值为1、2。mutil2++，指向数组中下一个元素：2
1*5
第二次比较：
2*2
1*3 三个数中的最小值为3，所以下一个丑数取3，那么数组中的值为1、2、3。mutil3++，指向数组中的下一个元素:2
1*5
第三次比较：
2*2
2*3 三个数中的最小值为4，所以下一个丑数取4，那么数组中的值为1、2、3、4。mutil2++，指向数组中的下一个元素：3
1*5
依此…
由上可以看出数据的比较就在三条路（乘2的一条路，乘3的一条路，乘5的一条路，变化的是三个索引）上的三个值比较，取到当前路上的值则当前路上的索引就自增一，还有一种情况是三条路上最小值不止一个，比如三条路为：3*2 、2*3、2*5，有两个都为6，那么mutil2++，mutil3++。

以下是代码：

    public int GetUglyNumber_Solution(int index) {
        if(index <= 0){
            return 0;
        }
        int[] uglyNum = new int[index];
        uglyNum[0] = 1;
        //建立三个索引，分别维护乘2、乘3、乘5大于uglyNum[i]中最小的数
        int mutil2 = 0;
        int mutil3 = 0;
        int mutil5 = 0;
        int i = 1;
        while(i != index){
            int tem = Math.min(Math.min(uglyNum[mutil2]*2,uglyNum[mutil3]*3),uglyNum[mutil5]*5);//求三个中的最小者，作为下一个丑数
            uglyNum[i] = tem;
            if(uglyNum[mutil2]*2 == tem) {mutil2++;}
            if(uglyNum[mutil3]*3 == tem) {mutil3++;}
            if(uglyNum[mutil5]*5 == tem) {mutil5++;}
            i++;
         }
        return uglyNum[index-1];
    }