【最小堆】【动态规划】力扣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]本身就是由许多因子组成）。