剑指Offer32 丑数（数字分解）

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

对于丑数C，定义其向量（x，y，z）。有 C = 2^x * 3^y * 5^z

初始化 丑数集合{1}
对于第i个丑数，肯定是由前i-1个丑数经过×2或x3或x5得到的。换句话说新的丑数产生必定基于已有的丑数中某三个数，这三个数可以重复。
比如：
i = 1，由{1}x2 {1}x3 {1}x5，基于三个数是（1,1,1）， 最小值2
i = 2，由{1,2}x2 {1,2}x3 {1,2}x5 观察可知，1x2 在i=1 的时候已经计算过，所以1x2舍去。再观察{1,2}x3 中1x3显然比2x3小，所以2x3舍去。同理2x5舍去，基于三个数是（2,1,1）取最小值3。
i = 3，基于（2,2,1）最小值4
i = 4，基于（3,2,1）最小值5
i = 5，基于（3,2,2）最小值6
i = 6，基于（4,3,2）最小值8
....
归纳：初始化，2,3,5三个基数都是丑数[0]值为1，当基数x2得到最小的数后，2的基数就要后移1位，取丑数[1]。依次类推。

    public int GetUglyNumber_Solution(int index) {
        if (index < 7) return index; // 0 1 2 3 4 5 6
        int[] ans = new int[index];
        ans[0] = 1;

        int p2 = 0, p3 = 0, p5 = 0; // 基数指针

        for (int i = 1; i < index; i++) {
            ans[i] = Math.min(ans[p2] * 2, Math.min(ans[p3] * 3, ans[p5] * 5));// 2,3,5分别和自己的基数相乘，取最小值
            if(ans[i] == ans[p2]*2) p2++; // 
            if(ans[i] == ans[p3]*3) p3++;
            if(ans[i] == ans[p5]*5) p5++;
        }
        return ans[index-1];
    }