剑指 offer 笔记 33 | 丑数

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

思路分析
根据丑数的定义，丑数只能被 2、3 和 5 整除。根据丑数的定义，丑数应该是另一个丑数乘以 2、3 或者 5 的结果（1除外）。

因此我们可以创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以 2、3 或者 5 得到的。

解释说明：

import java.util.*;
public class Solution
{
    public int GetUglyNumber_Solution(int n)
    {
      // 0-6的丑数分别为0-6
       if(n < 7) 
           return n;
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(1);
        //p2，p3，p5分别为三个队列的指针
        int p2 = 0, p3 = 0, p5 = 0;
        while(list.size()<n)
        {
            int m2 = list.get(p2)*2;
            int m3 = list.get(p3)*3;
            int m5 = list.get(p5)*5;
            int min = Math.min(m2,Math.min(m3,m5));
            list.add(min);
            if(min == m2)
                p2++;
            if(min == m3)
                p3++;
            if(min == m5)
                p5++;
        }
        return list.get(list.size()-1);
    }
}

链接：https://www.nowcoder.com/questionTerminal/6aa9e04fc3794f68acf8778237ba065b?f=discussion
来源：牛客网