剑指Offer第三十三题：丑数

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

解答：
刚看到这个题目，想的是丑数排序有什么样的规律，但是发现前一个丑数和后一个丑数似乎没有任何规律。
看了别人的题解，发现原来可以按一定规律排列出所有丑数的。
下面记录一下我的理解：
设置一个丑数有序队列Q
每一个丑数分别乘【2，3，5】可以产生3个丑数
设置三个队列，分别是2，3，5队列A，B，C
第一次迭代 Q=[1]
取Q中第一个数1分别2，3，5放入A，B，C中
A=[2]
B=[3]
C=[5]

第二次迭代
取出ABC中最小的数2放入Q，Q=[1,2]
取Q中第二个数2分别2,3,*5放入A，B，C中
A=[4]
B=[3,6]
C=[5,10]

依次往下最终Q
....
以这种方式可以排列出所有的丑数，虽然有重复的数字存在，但是在取最小值时可以去除重复数字。

public class Q_33 {

public int GetUglyNumber_Solution(int index) {
    if (index < 7) return index;
    int i = 0, m = 0, n = 0;
    int[] num = new int[index];
    num[0] = 1;
    for (int j = 1; j < index; j++) {
        num[j] = Math.min(num[i] * 2, Math.min(num[m] * 3, num[n] * 5));
        if (num[j] == num[i] * 2) i++;
        if (num[j] == num[m] * 3) m++;
        if (num[j] == num[n] * 5) n++;
    }
    return num[index - 1];
}
public static void main(String[] args) {
    System.out.println(new Q_33().GetUglyNumber_Solution(8));
}

}