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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ugly-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

比较容易理解的思路是使用优先队列，初始的第一个丑数为1，每产生一个丑数，就将其分别乘2、3、5后添加到优先队列，然后poll出优先队列最小的数，循环此操作，直至生成n个丑数。不过这样做有可能将重复的数入队，因此需要使用一个set记录已经入队的元素。实现见代码一。

代码

优先队列

class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> minHeap = new PriorityQueue();
        minHeap.offer(1L);
        int k = 0;
        int ans = 0;
        Set<Long> set = new HashSet<>();
        set.add(1L);
        while (k++ < n) {
            long num = minHeap.poll();
            ans = (int) num;
            if (!set.contains(2 * num)) {
                minHeap.offer(2 * num);
                set.add(2 * num);
            }
            if (!set.contains(3 * num)) {
                minHeap.offer(3 * num);
                set.add(3 * num);
            }
            if (!set.contains(5 * num)) {
                minHeap.offer(5 * num);
                set.add(5 * num);
            }
        }
        return ans;
    }
}

多路归并

官解将该方法贴了动态规划的标签，感觉还是多路归并更合适一些，主要是这个思想值得学习。「这个」题解讲的通俗易懂，这里不再叙述了。

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1;
        int p3 = 1;
        int p5 = 1;
        for (int i = 2; i <= n; ++i) {
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int 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];
    }
}