/**
1. 一个丑数只有2,3,5 三种因子, 所以必定是这三个因子的不同个数组合, 小丑数的2,3,5倍一定是大丑数, 大丑数也一定是由小丑数乘2,3,5得到的
2. 动态规划:
    2.1 状态定义: f[i] i是不是一个丑数
    2.2 状态计算: 以最后一个数i 划分集合:
        2.2.1 i % 2 == 0 ,  f[i] = f[i] || f[i/2];
        2.2.2 i % 3 == 0 ,  f[i] = f[i] || f[i/3];
        2.2.3 i % 5 == 0 ,  f[i] = f[i] || f[i/5];
    2.4 边界条件: f[~] = false;  f[1] = true;

3. 上述方法会超时, 因为整个数组中有很多空洞, 我们要更快的计算直接推断下一个丑数的位置, 可以用bfs的思想
    3.1 每次把数x的 x*2, x*3, x*5去重并放入堆中,  堆顶就是下一个最小的丑数
    3.2 每出堆一个数, 入堆最多3个数,  所以整体复杂度为 O(nlogn)

4. 每个丑数都是由之前某个数 *2 || * 3 || * 5 得到的, 而且每个数只能分别被2,3,5乘一次, 所以丑数序列的最小值是*2, *3, *5 序列的最小值
    4.1 可以直接用三个指针代表*2, *3, *5 序列, 取最小的加入即可
    4.2 不重不漏的扫描, O(n)

*/

class Solution {
    static final int maxN = 1690;
    public int nthUglyNumber(int n) {
        return scan(n);
        // return heap(n);
    }

    public int scan(int n){
        List<Integer> list = new ArrayList<>();
        list.add(1);
        int i2 = 0, i3 = 0, i5 = 0;
        while (list.size() < n){
            int x2 = list.get(i2) * 2;
            int x3 = list.get(i3) * 3;
            int x5 = list.get(i5) * 5;

            int next =  Math.min(x2, Math.min(x3, x5));
            list.add(next);

            if (next == x2) i2++;
            if (next == x3) i3++;
            if (next == x5) i5++;
        }
        return list.get(n-1);
    }

    public int heap(int n){
        Queue<Long> queue = new PriorityQueue<>(); 
        Set<Long> set = new HashSet<>();
        add(queue, set, 1L);
        while (!queue.isEmpty()){
            long top = queue.poll();
            if (--n == 0) return (int)top;
            add(queue, set, top * 2);
            add(queue, set, top * 3);
            add(queue, set, top * 5);
        }
        return 0;
    }

    private void add(Queue<Long> queue, Set<Long> set, long x){
        if (!set.contains(x)){
            set.add(x);
            queue.offer(x);
        }
    }

    public int dpTLE(int n){
        if (n == 1) return 1;
        List<Boolean> f = new ArrayList<>();
        f.add(false);
        f.add(true);
        for (int i = 2; n > 1 ; i++){
            f.add(false);
            if (i % 2 == 0) f.set(i, f.get(i) || f.get(i /2));
            if (i % 3 == 0) f.set(i, f.get(i) || f.get(i /3));
            if (i % 5 == 0) f.set(i, f.get(i) || f.get(i /5));
            if (f.get(i))  n--;
            if (n == 1) return i;
        }
        return 1;
    }
}