丑数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.com/problems/ugly-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

建议先阅读丑数I的题目作为了解：https://leetcode-cn.com/problems/ugly-number/

二、题解：

1、动态规划：

实际上，最容易想到的解法就是动态规划，毕竟这种新数字可以用之前的数据推出摆明了就是动态规划。

那么我们该怎么建立状态转移方程呢?其实这个应该从丑数的性质开始探讨：

“丑数 就是只包含质因数 2、3 和/或 5 的正整数。”

因此我们新的数字肯定是要用之前的某数乘上2，3或5得到的，并且因为题目要求是升序排列，那么不难得出dp【i】=max{num1*2，num2*3，num3*5}这个方程。

那么现在新的问题又出现了：这三个数该如何确定呢？

这里我们采用三指针（a，b，c）的方法：初始位置都是第一个数，每一个指针只会单一地将所指向的数乘上2，3或者5。一旦找出max{dp【a】*2，dp【b】*3，dp【c】*5}，就将对应的指针后移。这里用C写一个判断：

int tar=min(dp[a]*5,dp[b]*3,dp[c]*2);
       if(tar==dp[a]*5) 
       a++;
	   if(tar==dp[b]*3) 
       b++;
       if(tar==dp[c]*2) 
       c++;
       dp[i]=tar;

这里注意三个指针乘2，3或5后的值都要参与判断，目的是为了将与最小值相等的所有指针都后移从而避免重复的情况。

！：为何后移？

我们说过丑数是由之前的数乘2，3，5得到的，因此得到最小值后，该指针指向的数就已经没有再乘对应数的价值了（比如说a指针对应乘2，被选取后这个最小值就已经在dp队列里了，因此就可以丢弃了即a++），而其它的不变（因为丑数数列是定的，我们只是把他写出来，所有的丑数都会用上，所以上一次未成为最小值的数一定会在未来成为某位置的最小数）。

2、最小堆：

用最小堆的优点是易于理解，仅需要用一个哈希表进行查重工作防止重复输出，剩下的就是模板化的堆运算，但是缺点也太明显了要写好多内容呜呜呜，并且时间复杂度为O(nlogn)远高于动态规划。

每次拿出最顶端的数，存入对应乘以2，3，5后的数（三个），以此类推。

最小堆 构建、插入、删除的过程图解：

https://blog.csdn.net/hrn1216/article/details/51465270?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161812713416780357267485%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=161812713416780357267485&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-51465270.first_rank_v2_pc_rank_v29&utm_term=%E6%9C%80%E5%B0%8F%E5%A0%86

之后学习堆这一部分时会再详细整理一下各种理论知识与细节，数据结构的氵还是挺深的