传送门：https://leetcode-cn.com/problems/ugly-number-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 通常被视为丑数。

解题思路：最小堆

要得到从小到大的第 n 个丑数，可以使用最小堆实现。初始时堆为空。

  1. 将最小的丑数 1 加入堆。

  2. 取出堆顶元素 x，则 x 是堆中最小的丑数，由于 2x, 3x, 5x 也是丑数，因此将2x, 3x, 5x 加入堆。

    1.                                      如：2×3、3×2<br />上述做法会导致堆中出现**重复元素**的情况。可以使用哈希集合去重，避免相同元素多次加入堆。<br />在去重条件下，第 `n` 次从最小堆中取出的元素即为第 `n` 个丑数。

复杂度分析

时间复杂度：🚩[LeetCode]dp264 丑数II - 图1

得到第 n 个丑数需要进行 n 次循环，每次循环都要从最小堆中取出 1 个元素以及向最小堆中加入最多 3 个元素，因此每次循环的时间复杂度是 🚩[LeetCode]dp264 丑数II - 图2，总时间复杂度是 🚩[LeetCode]dp264 丑数II - 图3。

空间复杂度：🚩[LeetCode]dp264 丑数II - 图4。
空间复杂度主要取决于最小堆和哈希集合的大小，最小堆和哈希集合的大小都不会超过 3n。

解题思路：动态规划

定义数组 dp[]，其中 dp[i] 表示第 i 个丑数，第 n 个丑数即为 dp[n] 。

解题关键：我们要知道，所有的丑数一定由丑数产生 。
**

[ 1，2，3，4，5，6，8，9，10，12 ，….] 丑数的质只有2、3、5 12=2 13=3 15=5 22=4 2*3=6 25=10 32=6 * 33=9 3*5=15 会有重复，所以要去重

边界条件：最小的丑数是 1，因此 dp[1]=1 。

如何得到其他的丑数呢？
**
定义三个指针 🚩[LeetCode]dp264 丑数II - 图5，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时，三个指针的值都是 1 。
当 🚩[LeetCode]dp264 丑数II - 图6 时，令 🚩[LeetCode]dp264 丑数II - 图7，分别比较 🚩[LeetCode]dp264 丑数II - 图8 和 🚩[LeetCode]dp264 丑数II - 图9、🚩[LeetCode]dp264 丑数II - 图10和 🚩[LeetCode]dp264 丑数II - 图11是否相等，如果相等则将对应的指针加 1。

复杂度分析

时间复杂度：🚩[LeetCode]dp264 丑数II - 图12，需要计算数组 🚩[LeetCode]dp264 丑数II - 图13 中的 🚩[LeetCode]dp264 丑数II - 图14 个元素，每个元素的计算都可以在 🚩[LeetCode]dp264 丑数II - 图15 的时间内完成。

空间复杂度：🚩[LeetCode]dp264 丑数II - 图16。
空间复杂度主要取决于数组 🚩[LeetCode]dp264 丑数II - 图17 的大小 。

代码

我的代码

public class dp264 {
    public static int nthUglyNumber(int n) {
        //丑数2,3,5
        int[]dp=new int[n];
        dp[0]=1;
        int p2=0,p3=0,p5=0,nums=0;
        while(++nums<n){
            dp[nums]=Math.min(Math.min(dp[p2]*2,dp[p3]*3),dp[p5]*5);
            if (dp[nums] == dp[p2]*2) {
                p2++;
            }
            if (dp[nums] == dp[p3]*3) {
                p3++;
            }
            if (dp[nums] ==dp[p5]*5) {
                p5++;
            }
           // int i= (dp[nums]==dp[p2]*2)?++p2: ((dp[nums]==dp[p3]*3)?++p3:++p5);//不能压缩代码
        }
        return dp[n-1];
    }

    public static void main(String[] args) {
        System.out.println(nthUglyNumber(111));
    }
}