【剑指offer】丑数

题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
1、思路分析
首先，丑数可以分解为2^x3^y5^z，x,y,z均大于等于0。我们的思路是按照大小依次求出前n个丑数，返回最后一个。首先将存储丑数的数组初始化为1，并设三个指针i2,i3,i5，均初始化为0，指示用哪个位置的元素来乘2、3、5，以此保证添加丑数的大小顺序。i2,i3,i5的更新规则为：此前添加的丑数乘的是哪一个因数，哪个因数对应的指针就加1。
2、代码

import java.util.ArrayList;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index == 0) return 0;
        ArrayList<Integer> res = new ArrayList<>();
        res.add(1);
        int i2=0,i3=0,i5=0;
        while(res.size()<index){
            int m2 = res.get(i2)*2;
            int m3 = res.get(i3)*3;
            int m5 = res.get(i5)*5;
            int min = Math.min(m2,Math.min(m3,m5));
            res.add(min);
            if(m2 == min) i2++;
            if(m3 == min) i3++;
            if(m5 == min) i5++;
        }
        return res.get(res.size()-1);
    }
}