LeetCode_动态规划_中等_264.丑数 II

1.题目

给你一个整数 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ugly-number-ii

2.思路

（1）暴力穷举法
暴力穷举法比较容易想到：
① 如果 n == 1，则直接返回 1，因为 1 通常被视为丑数；
② 否则从正整数 x = 2 开始判断，具体的判断方式可以参考LeetCode_263.丑数这篇文章，如果当前的数是丑数，则 n–，当 n == 1 时停止判断，此时的 x - 1 就是第 n 个丑数。不过该方法的时间复杂度较高，在 LeetCode 上提交时会出现“超出时间限制”的提示！

（2）最小堆
思路参考本题官方题解。

（3）动态规划
思路参考本题官方题解。

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {
    
    public int nthUglyNumber(int n) {
    
        int[] factors = {
    2, 3, 5};
        if (n == 1) {
    
            // 1 通常被视为丑数
            return 1;
        }
        //从正整数 2 开始判断
        int x = 2;
        int i = 1;
        while (n > 1) {
    
            int tmp = x;
            for (int j = 0; j < factors.length; j++) {
    
                while (tmp % factors[j] == 0) {
    
                    tmp /= factors[j];
                }
            }
            if (tmp == 1) {
    
                n--;
            }
            //判断下一个正整数
            x++;
        }
        return x - 1;
    }
}

//思路2————最小堆
class Solution {
    
    public int nthUglyNumber(int n) {
    
        int[] factors = {
    2, 3, 5};
        if (n == 1) {
    
            // 1 通常被视为丑数
            return 1;
        }
        Set<Long> hashSet = new HashSet<>();
        PriorityQueue<Long> heap = new PriorityQueue<>();
        hashSet.add(1L);
        //初始时堆为空，首先将最小的丑数 1 加入堆
        heap.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
    
            // 每次取出堆顶元素 x，则 x 是堆中最小的丑数
            long x = heap.poll();
            ugly = (int) x;
            for (int factor : factors) {
    
                /* 由于 2x, 3x, 5x 也是丑数，因此将 2x, 3x, 5x 加入堆 该做法会导致堆中出现重复元素的情况，为了避免重复元素，这里使用哈希集合去重 在排除重复元素的情况下，第 n 次从最小堆中取出的元素即为第 n 个丑数 */
                long next = x * factor;
                if (hashSet.add(next)) {
    
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }
}

//思路3————动态规划
class Solution {
    
    public int nthUglyNumber(int n) {
    
        // dp[i] 表示第 i 个丑数
        int[] dp = new int[n + 1];
        // 最小的丑数为 1
        dp[1] = 1;
        //定义三个指针，表示下一个丑数是当前指针指向的丑数乘以对应的质因数
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
    
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) {
    
                p2++;
            }
            if (dp[i] == num3) {
    
                p3++;
            }
            if (dp[i] == num5) {
    
                p5++;
            }
        }
        return dp[n];
    }
}