[TOC]

一、题目描述

编写一个程序，找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例：

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明：

1 是丑数。
n 不超过1690。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ugly-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题方法

1. 暴力法

思路：

最原始的暴力法，令表示第个丑数的实际数值，则对于从的每一个数字，我们都令它对、、做因式分解，来判定他是否为丑数，直至找到第个丑数。
粗略估算，一个计算的上界是。
进一步的简化估算，我们可以得到时间复杂度：，空间复杂度：。

2. 记忆化搜索

思路：

我们重新思考一下题目，丑数的定义是“只包含质因数 2, 3, 5 的正整数”。
那反过来说，"若为大于的丑数，则，，中至少有一个是丑数"。
利用这这一点，我们可以得到一个递推方程：

初始条件有，令表示第个丑数的实际数值，则对于，我们都可以在常数时间内判断出它是否为丑数，但我们需要保存中的每一个数字，以方便之后的快速判断。

时间复杂度：，空间复杂度：

3. 递推

思路：

上述两个方法，都需要计算个数字，考虑到丑数虽然前期分布比较密集，但到后期相对就会稀疏很多，因而这样的计算量有些浪费。

在方法2中，我们提到，“若为大于的丑数，则，，中至少有一个是丑数”，并且给出了递推方程。但观察递推方程，我们可以明显地看到，需要进行的判断太多了，不够优雅。
这句话如果反过来说就是，“若为丑数，则、、都是丑数”。

可以利用这一点进行迅速递推，对于每一个丑数，我们都可以得到三个新的丑数，那么对于第个丑数，必定会在至多次乘法计算中出现（某些丑数会被计算多次，比如6可以分别由2和3递推得到）。

嗯？等等，存在重复？存在重复不利于我们计算第个吧？因为谁知道前面出现了多少重复？必须得把重复去掉。
那么，怎么去重复呢？常见的手段，自然就是使用哈希表来做标记了。

至此，我们已经完成了查重的判断了。下一个步骤就是在一堆没有重复的丑数当中，取出第大的丑数。

那么，该怎么做呢？

由于我们是要求第个丑数，换句话说就是要求这些丑数中第小的。这样我们不由自主地会想到对数组排序，或者直接使用堆。
进一步的，显然我们希望每一次都拿出还未进行递推的丑数中最小的那一个进行递推(这样能避免真的每次都递推到)。
结合二者，于是这里决定选择堆来处理。进一步的，因为每次都要取出最小的，我们决定使用小顶堆来处理。

对于每一个丑数，递推出三个新的丑数复杂度为，哈希表中查重平均复杂度为，取堆顶部元素复杂度为，往堆中插入和删除元素复杂度都为，而外循环共需执行次。

于是我们有，总的时间复杂度：，总的空间复杂度：。

代码：

class Solution {
public:
    int nthUglyNumber(int n) {
        if (n < 7)      return n;

        priority_queue<unsigned long long, vector<unsigned long long>, greater<unsigned long long>> q;
        unordered_set<unsigned long long> s;
        q.push(1);
        s.insert(1);
        while (--n) {
            auto num = q.top();
            q.pop();
            if (s.find(num * 2) == s.end()) {
                q.push(num * 2);
                s.insert(num * 2);
            }
            if (s.find(num * 3) == s.end()) {
                q.push(num * 3);
                s.insert(num * 3);
            }
            if (s.find(num * 5) == s.end()) {
                q.push(num * 5);
                s.insert(num * 5);
            }
        }
        return q.top();
    }
};

4. 动态规划

思路：

方法3是已经足够解决问题了，但总觉得好像还不够看。
为了判断重复而单独使用了一个哈希表，对于强迫真来说这真的令人坐立不安。有没有什么办法能取消掉那个哈希表？

既然想要去掉哈希表，那么首先肯定得搞清楚这里的哈希表有什么用。正如方法3所属，因为递推的时候很可能递推到重复的数字，所以我们使用哈希表进行去重。
那么想去掉哈希表，问题就转化成了，如何避免递推到重复的数字。

要避免递推到重复的数字，我们可以将计算目标转换为当前这个丑数，而不是递推出的另外三个丑数。记当前正在计算的第个丑数为。根据丑数的定义，我们知道，除以外的丑数，或者是某个丑数乘以，或者是某个丑数乘以，或者是某个丑数乘以。如果分别设这三个数字为、、，我们一定有（因为升序，所以每个丑数因该是能得到的最小值）。

于是进一步的，问题又转化为如何获得并维护、、。由于起初的三个丑数、、可以看作是、、，所以最初、、都可以设置为。那么接着当计算出一个新的丑数的时候，该如何对、、进行维护呢？可以想象一下，以为例，当时，显然已经不足以用去递推，因而我们应该将设置为比大的丑数。同时为了保证尽可能地小，应该仅仅向后移动一位，更新为仅次于的丑数。和同理。

时间复杂度：，空间复杂度：。

代码：

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n, numeric_limits<int>::max());
        vector<int> ptr(3, 0);
        vector<int> primes = { 2, 3, 5 };
        dp[0] = 1;
        for (auto i = 1; i < n; ++i) {
            for (auto j = 0; j < 3; ++j)
                dp[i] = min(dp[i], dp[ptr[j]] * primes[j]);
            for (auto j = 0; j < 3; ++j)
                if (dp[i] >= dp[ptr[j]] * primes[j])
                    ptr[j]++;
        }
        return dp[n - 1];
    }
};