[数据结构与算法]【LeetCode剑指offer49】丑数（小顶堆或DP）

一、题目

二、思路

方法一：小顶堆
求前k大经常用到优先级队列，小顶堆，循环将符合要求的丑数加入小顶堆，取k次堆顶元素即可让堆顶为第k个丑数。而逐个加入丑数即加入$2x$、$3x$、$5x$进入集合（去重）即可。注意这里加入小顶堆的元素不能是int类型，否则会报错overflow（因为next = temp * factor后可能会越界）：

Line 17: Char 33: runtime error: signed integer overflow: 429981696 * 5 cannot be represented in type 'int' (solution.cpp)

三、方法一：小顶堆

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> fac = {2, 3, 5};
        //用int还不够
        unordered_set<long>s;
        //注意小顶堆用greater
        priority_queue<long, vector<long>, greater<long>>min_heap;
        s.insert(1L);
        min_heap.push(1L);
        int ugly = 0;
        for(int i = 0; i < n; i++){
            long temp = min_heap.top();
            min_heap.pop();
            ugly = (int)temp;
            for(int factor: fac){
                long next = temp * factor;
                if(!s.count(next)){
                    s.insert(next);
                    min_heap.push(next);
                }       
            }
        }
        return ugly;
    }
};

四、方法二：动态规划

方法二：动态规划
小顶堆会预存较多丑数，维护小顶堆的时间和空间复杂度较高。

简单说就是把所有丑数列出来，然后从小到大排序。而大的丑数必然是小丑数的2/3/5倍，所以有下面这3个数组。每次就从那数组中取出一个最小的丑数归并到目标数组中。

nums2 = {1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2...}
nums3 = {1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3...}
nums5 = {1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5...}
// 注意 7 不是丑数. 
// 2, 3, 5 这前 3 个丑数一定要乘以其它的丑数， 所得的结果才是新的丑数， 所以上例中没有出现 7*2, 7*3, 7*5

现在问题其实转化为合并3个上面这样的有序序列，常规方法即每个序列各维护一个指针，然后每次将最小的元素加入数组中，并且此时要将对应指针后移一个元素，具体根据动态规划的四部曲分析：

（1）确定状态
定义数组 $dp[i]$，其中 $dp[i]$ 表示第 i 个丑数，第 n 个丑数即为 $dp[n]$。

（2）状态转移方程：n大于等于2时：$$dp[i]=\min \left(dp\left[p_2\right]\times 2,dp\left[p_3\right]\times 3,dp\left[p_5\right]\times 5\right)$$

（3）边界+初始条件：最小的丑数是1，dp[1]=1。

（4）计算顺序：从小到大遍历。

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