【最小堆】【动态规划】力扣264. 丑数 II

方法一：堆

class Solution {
public:int nthUglyNumber(int n) {vector<int> factors = {2, 3, 5};unordered_set<long> seen;priority_queue<long, vector<long>, greater<long>> heap;seen.insert(1L);heap.push(1L);int ugly = 0;for(int i = 0; i < n; i++){long curr = heap.top();heap.pop();ugly = (int)curr;for(int factor : factors){long next = curr * factor;if(!seen.count(next)){seen.insert(next);heap.push(next);}}}return ugly;}
};

时间复杂度：O(nlogn)。得到第 n 个丑数需要进行 n 次循环，每次循环都要从最小堆中取出 1 个元素以及向最小堆中加入最多 3 个元素，因此每次循环的时间复杂度是 O(log(3n)+3log(3n))=O(logn)，总时间复杂度是 O(nlogn)。

空间复杂度：O(n)。空间复杂度主要取决于最小堆和哈希集合的大小，最小堆和哈希集合的大小都不会超过 3n。

我们可以使用堆来模拟丑数的情况，我们定义一个堆，堆顶是最小的数，这个时候我们让堆顶的数乘以factors的三个不同因子的情况，继续加入到堆中，然后将堆顶元素弹出，这个时候堆顶元素就是第二小的数（包含已弹出的最小数），也就是第二个丑数，然后不断继续将堆顶元素乘以factors中顶三个不同因子，得到更多丑数。由于我们遍历了n次，要遍历第n次的时候，前面已经弹出了n-1个丑数，那么第n个数就是第n个丑数。有人可能会问那么有重复的丑数怎么办，那就定义一个哈希集合检查，如果乘以因子后的丑数已经出现在哈希集合中，那么就不会推入到堆里。

---

方法2:动态规划

class Solution {
public:int nthUglyNumber(int n) {vector<int> dp(n+1);dp[1] = 1;int p2 = 1, p3 = 1, 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] = min(min(num2, num3), num5);if(dp[i] == num2){p2++;}if(dp[i] == num3){p3++;}if(dp[i] == num5){p5++;}}return dp[n];}
};

时间复杂度：O(n)。需要计算数组 dp 中的 n 个元素，每个元素的计算都可以在 O(1) 的时间内完成。

空间复杂度：O(n)。空间复杂度主要取决于数组 dp 的大小。

这个动态规划的思路就是，每一个丑数都可以乘以2、3、5中的某一个因子变成另外一个数，然后由于节省空间，我们用指针来记录将哪一个丑数放在dp哪个位置。

举个例子，dp[1]为1，这时候三个指针都指向1，我们要找dp[2]要放什么呢？这时候有1x2=2, 1x3=3, 1x5=5。这时候我们要将他们正确插入到dp中，这时候就找其中最小的数也就是2放到dp[2]中，dp[2]中放的是1x2。继续找dp[3]要存放什么呢，这个时候有1x3=3, 1x5=5,还有dp[2]乘以2也就是1x2 x 2=4。那么三者中3最小，所以dp[3]中存放的是1x3=3，这个时候令p3++指向2。

通过上面我们可以明白，每一个dp[i]存放的实际上都是从1开始不断乘以某个因子后形成的丑数，如1x2或者1x3或者1x2x2之类的数，而我们要做的，就是将还没计算过的dp[i]乘以各个因子（dp[i]本身就是由许多因子组成）。