寻找丑数

寻找第N个丑数

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

题意

只包含质因子 2，3，5的数，什么叫质因子？肯定是质数啊，只能被1或者自身整除的数称为质数！意思就是这个数他只能被2，3，5这三个质数整除，如果被其他质数整除就不是丑数了，比如14，可以被7整除。8也是丑数，因为8里面的质因子只有2，4并不是质数。

解题

怎么寻找？一般思路，从1开始递增，如果这个数不能被2，3，5整除肯定不为丑数，否则一直除以2 或者除以3 或者除以5，最后结果为1，代表这个数是丑数，如19不能整除不是丑数，18 = 18/2=9/3=3/3=1一直能被整除最后结果为1，肯定是丑数。对于每一个数都这么做，时间复杂度太高，肯定不是最优解。
换个思路一个丑数 *2 或者丑数 3 或者丑数5 肯定还是丑数！
我们从1开始，求第二个丑数怎么做呢?
肯定是1x2 1x3 1x5，取最小值，为1x2 = 2；
第二个丑数找到了！。第三个呢？
同样的思路 1x2，1x3 1x5 ？不对了！1x2已经被计算过了！
所以我们在用一个丑数x质数因子（2，3，5）计算过下一个丑数的时候，下次计算的时候就不能再用它乘以相同的质数因子了！比如这里的1x2 不能再加入选项了，这时候你需要把丑数下移到下一个，比如2 x 2,2这个丑数没有和2相乘过。
得到原理之后代码就很简单了
我们需要用三个下标，来表示这个下标的丑数是否和2，3，5相乘过，如果相乘过，我就把下标+1,既然通过下标找值肯定需要额外的数组空间。

 public int GetUglyNumber_Solution(int index) {
        int[] uglyArray = new int[index];
        uglyArray[1] = 0;
        //下一个丑数肯定是在第一个的基础上乘以2或者乘以3 或者乘以5
        //取其最小值
        int currentIndex = 1;
        //开始循环查找
        //丑数= 丑数*丑数 没有其他的方式，只能是丑数*丑数得到
        //这三个下标代表的意思就是，每一次使用当前下标取进行丑数计算，都需要把下标+1
        //计算下一个丑数的流程，比如通过求第二个丑数
        //我们第一个丑数是1，第二个丑数肯定是1 * 2 1*3 1*3的最小值 计算得出为2
        //在计算第三个丑数 这时候我们肯定不能计算 1*2了因为1*2已经计算过了！
        //所以我们用过一个丑数进行计算的时候，下次计算的时候，就需要把数组下标加一 防止重复计算 比如这时候我们计算的是 2*2
        //同理，对于3 和5我们也需要一个下标来保存当前使用的丑数到第几个了。
        //
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        while (currentIndex < index){
            int temp = midValue(uglyArray[p2] * 2,uglyArray[p3] * 3,uglyArray[p5] * 5);
            uglyArray[currentIndex] = temp;
            if ( temp == uglyArray[p2] * 2){
                //是通过2 计算的 下标+1
                p2++;
            }
            if ( temp == uglyArray[p3] * 3){
                //是通过2 计算的 下标+1
                p3++;
            }
            if ( temp == uglyArray[p5] * 5){
                //是通过2 计算的 下标+1
                p5++;
            }
            currentIndex++;
        }

        return uglyArray[index-1];
    }
    public int midValue(int a,int b,int c){
        return Math.min(a,Math.min(b,c));
    }