leetcode 264 丑数 II

题意简述

定义因子只有$2$或$3$或$5$的数为丑数，求第$n$个丑数。

算法分析

法一 最小堆

每次取出堆顶$x$，插入$2x,3x,5x$。set或priority_queue。复杂度$nlogn$。

法二 动态规划

每个丑数，乘以$2$乘以$3$乘以$5$都能得到$3$个更大的丑数。反过来看每个丑数，都是由之前的某个丑数乘以$2$乘以$3$乘以$5$得到。为了得到$f[i]$是由哪一个推得，考虑维护$p_2p_3p_5$三个指针，分别指向当前乘以$2$乘以$3$乘以$5$之后可能更新最大丑数（即$f[i-1]$）的之前的某个丑数下标。

定义$f[i]$为第$i$个丑数，指针$p_x(x=2,3,5)$为

$$min\\{j\\} \quad s.t. \ f[j] \times x > f[i - 1]$$

每次求第$i$个丑数时，取

min\left\\{ f[p_x] \times x \right\\}

之后比较$f[i]$与$f[p_x] \times x(x=2,3,5)$，将对应的指针加一。

举例来看，第一个丑数$1$，有资格乘以$2$乘以$3$乘以$5$，取出$2$作为第二个丑数。之后，由于$1$已经乘以过$2$，$1$只有乘以$3$乘以$5$的资格（可能性）了，对应的操作就是$p_2$加一。

从另一个角度看，为什么这样选择$p_x$就一定是能更新最大丑数的最小下标呢？这是因为只有当$f[i]=f[p_x] \times x$时才会移动$p_x$。也就是说，对于任意一个小于$p_x$的下标$p$，$f[p] \times x$一定被考虑过了（已经出现在$f$里面了），自然也就无法超过$f[i - 1]$。

代码实现

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> f(1700, 0);
        int p2 = 1, p3 = 1, p5 = 1;
        f[1] = 1;

        for (int i = 2; i <= n; i++) {
            f[i] = min({f[p2] * 2, f[p3] * 3, f[p5] * 5});
            if (f[i] == f[p2] * 2) p2++;
            if (f[i] == f[p3] * 3) p3++;
            if (f[i] == f[p5] * 5) p5++;
        }
        return f[n];
    }
};