丑数 II

264. 丑数 II

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是质因子只包含 2、3 和 5 的正整数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

提示：

• 1 <= n <= 1690

1、优先队列

class Solution {
    public int nthUglyNumber(int n) {
        int[] arr = {2,3,5};
        Set<Long> set = new HashSet();
        Queue<Long> que = new PriorityQueue();
        set.add(1L);
        que.add(1L);
        long x = 1;
        for(int i = 0;i < n; i++){
            x = que.poll();
            for(int num : arr){
                long t = num*x;
                if(!set.contains(t)){
                    set.add(t);
                    que.add(t);
                }
            }    
        }
        return (int)x;
    }
}

2、类似于暴力

class Solution {
    static int[] dp = new int[1691];

    public int nthUglyNumber(int n) {
        if (dp[1] == 0) { // 第一次
            dp[1] = 1;
            int p2 = 1, p3 = 1, p5 = 1;
            for (int i = 2; i <= 1690; i++) {
                // 要保证是递增的，因此只要一个数还没被用过，其对应的位置就别动。
                int num2 = 2 * dp[p2];
                int num3 = 3 * dp[p3];
                int num5 = 5 * dp[p5];
                dp[i] = Math.min(num2, Math.min(num3, num5));
                if (dp[i] == num2) { // 这个数字用过了，就动
                    p2++;
                }
                if (dp[i] == num3) {
                    p3++;
                }
                if (dp[i] == num5) {
                    p5++;
                }
            }
        }
        return dp[n];
    }
}