面试题34：丑数
题目
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
暴力解法
从1开始步长为1，逐个判断是否为丑数。效率太低
根据丑数的规则，直接生成丑数序列
假如我们已经有了从1到k的丑数，如何生成k到N的丑数呢？
问题就在于第k+1个丑数是怎么生成的？
一个想法是从第一个丑数开始，依次乘以2、3、5，直到出现大于第k个丑数。
但这样又有很多不必要的计算。
假设我们从第一个丑数开始，依次乘以2、3、5，直到出现大于第k个丑数，此时这个位置能否直接用于第k+2个数的生成呢？而不是每次都从第一个丑数开始计算。
顺着这个思路比较难想清楚。换个思路
每个丑数的出现必定是前面的丑数乘以2或者3或者5。我们先对前面的每个丑数都依次乘以2，直到遇到大于第k个丑数的情况，并记下这个位置；然后对前面的每个丑数都依次乘以3，直到遇到大于第k个丑数的情况，并记下这个位置；然后对前面的每个丑数依次乘以5，直到遇到大于第k个丑数的情况，并记下这个位置。这样我们就有了三个大于第k个丑数的新的丑数，那么谁是第k+1个丑数呢？当然是三者中较小的那个。然后第k+2的丑数可以接着前面的工作来。
public int GetUglyNumber_Solution(int index) {
ArrayList<Integer> result = new ArrayList<>();
result.add(1);
int nextUgly = 0;
int index2 = 0;
int index3 = 0;
int index5 = 0;
while(index!=result.size()){
int min = result.get(index2)*2<result.get(index3)*3?result.get(index2)*2:result.get(index3)*3;
min = min<result.get(index5)*5?min:result.get(index5)*5;
result.add(min);
nextUgly++;
while(result.get(index2)*2<=result.get(nextUgly)){
index2++;
}
while (result.get(index3)*3<=result.get(nextUgly)){
index3++;
}
while (result.get(index5)*5<=result.get(nextUgly)){
index5++;
}
}
return result.get(index-1);
}
用三个指针的好处就是可以记录进度，想用一个指针完成记录进度的工作是不可能的。
