丑数

题目描述

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

分析

从1出发，分别乘2、3、5即可得到第一批2、3、5三个丑数。再从这三个丑数出发分别乘以2、3、5又可以得到9个丑数，但这样可能存在重复的且是无序的。

可以将每次乘2、3、5得到的数的最小的数放入列表，同时记录当前乘2、3、5使用的是队列中第i小的数字。依次往后对比。

实现

public int GetUglyNumber_Solution(int n) {
    if(n<=0)return 0;
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(1);
        int i2 = 0,i3 = 0,i5 = 0;
        while(list.size() < n)
        {
            int m2=list.get(i2)*2;
            int m3=list.get(i3)*3;
            int m5=list.get(i5)*5;
            // 对比得出本次的最小值
            int min=Math.min(m2,Math.min(m3,m5));
            list.add(min);
            // 更新位置
            if(min==m2)i2++;
            if(min==m3)i3++;
            if(min==m5)i5++;
        }
        return list.get(list.size()-1);
    }