剑指offer第三十三题。

题目描述

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

解题思路

刷着刷着越发觉得智商不够用了。。。这个解题思路相当于准备三个队列。第一个队列里面放的都是2的倍数，第二个队列放的都是3的倍数，第三个队列放的都是5的倍数。依次拿最前面的数，找出最小的，对应的索引加一。这样，就可以将只包含因子2，3，5的数按照从小到大的顺序拿出来了。智商确实是硬伤，这谁顶得住？

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.ArrayList;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0){
            return 0;
        }
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        int i2 = 0,i3 = 0,i5 = 0;
        while(list.size() < index){
            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(m2 == min)
                i2++;
            if(m3 == min)
                i3++;
            if(m5 == min)
                i5++;
        }
        return list.get(index-1);
    }
}