49-丑数

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

丑数是只包含2 3 5因子的数，因此我们考虑以1作为起点，反复对现有丑数乘以 2 3 5然后取其最小值重新放到数组中，这样反复迭代即可求出指定位置的丑数。

1 丑数数组 1

乘以2队列 2

乘以3队列 3

乘以5队列 5

我们取上面三个队列中的队头元素中的最小值放到丑数数组中

2 丑数数组 1 2

乘以2队列 4

乘以3队列 3 6

乘以5队列 5 10

3 丑数数组 1 2 3

乘以2队列 4 6

乘以3队列 6 9

乘以5队列 5 10 15

4 丑数数组 1 2 3 4

乘以2队列 6 8

乘以3队列 6 9 12

乘以5队列 5 10 15 20

5 丑数数组 1 2 3 4 5

乘以2队列 6 8 10

乘以3队列 6 9 12 15

乘以5队列 10 15 20 25

队头里有两个同样的6 需要都去掉

6 丑数数组 1 2 3 4 5 6

乘以2队列 8 10 12

乘以3队列 9 12 15 18

乘以5队列 10 15 20 25 30

其实我们没有必要维护三个队列，只需要维护三个指针即可。

丑数

后面的丑数一定是前面的某个丑数 乘以2或3 或5得到的。我们用三个指针，分别表示乘以2 乘以3 乘以5，然后比较得到最小值放到丑数数组中，同时对应的指针后移一位即可。

public int GetUglyNumber_Solution(int index) {
        int[] data = new int[index + 1];
        data[1] = 1;
        int factor2Index = 1;
        int factor3Index = 1;
        int factor5Index = 1;
        for (int i = 1; i < index; i++) {
            int min = min(data[factor2Index] * 2, data[factor3Index] * 3, data[factor5Index] * 5);
            data[i + 1] = min;
            if (data[factor2Index] * 2 == min) {
                factor2Index++;
            }
            if (data[factor3Index] * 3 == min) {
                factor3Index++;
            }
            if (data[factor5Index] * 5 == min) {
                factor5Index++;
            }

        }
        return data[index];
    }
    private int min(int a, int b, int c) {
        return min(min(a, b), c);
    }
    private int min(int a, int b) {
        return a > b ? b : a;
    }