丑数

题目描述

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

思路：

1. 容易想到的一种解法是，从1开始遍历，如果当前的数字能够被2整除，就连续除以2，如果当前的数字能够被3整除，就连续除以3，如果当前的数字能够被5整除，就连续除以5，如果最后的结果等于1，说明这个数是丑数。时间复杂度比较高
2. 每个丑数必然是前面的丑数乘以2或者乘以3或者乘以5得到的。所以我们大可不必遍历所有数字。但是问题来了？如果我们用数组保存已知的丑数，如果确保得到的丑数是排好序的？为此我们需要维护三个索引，p2、p3、p5，每次更新一个丑数就是在2p2、3p3、5*p5中选出最小的数并且更新p2、p3、p5的值。具体见Java代码

代码：

public int GetUglyNumber_Solution(int index) {
        /*
         所有的丑数必然是靠前的丑数乘以2或者乘以3或者乘以5得来，第一个丑数是1，维护一个数组就行了
        */
       if(index<1){
           return 0;
        }
        int[] uglys=new int[index];
        int uglyIndex=1;
        uglys[0]=1;

        int pMultiply2=0;
        int pMultiply3=0;
        int pMultiply5=0;

        while(uglyIndex<index){
            int nextUgly=min(uglys[pMultiply2]*2,uglys[pMultiply3]*3,uglys[pMultiply5]*5);
            uglys[uglyIndex]=nextUgly;
            uglyIndex++;

            while(uglys[pMultiply2]*2<=nextUgly)
                pMultiply2++;
            while(uglys[pMultiply3]*3<=nextUgly)
                pMultiply3++;
            while(uglys[pMultiply5]*5<=nextUgly)
                pMultiply5++;
        }
        return uglys[uglyIndex-1];
    }

    private int min(int a,int b,int c){
        return Math.min(Math.min(a,b),c);
    }