给你一个整数 n ，请你找出并返回第 n 个 丑数 。

**说明：**丑数是只包含质因数 2、3 或 5 的正整数；1 是丑数。

示例 1：

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

提示：

1 <= n <= 1690

首先可以知道，后面的丑数都是由前面的丑数乘以2或3或5得到的，但是我们不知道先出现的是哪个数乘以哪个值

可以考虑维护一个最小堆，同时使用哈希表避免重复，这样相当于我们是先求值再排序，直到能确定位置的丑数的个数达到n个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue<long, vector<long>, greater<long>> q;
        q.push(1);
        unordered_map<long, bool> hash;
        hash[1] = true;
        vector<long> flag = {2, 3, 5};
        long mid;
        while (n) {
            mid = q.top();
            for (int i = 0; i < 3; i++) {
                long midmid = mid * flag[i];
                if (!hash[midmid]) {
                    q.push(midmid);
                    hash[midmid] = true;
                }
            }
            q.pop();
            n--;
        }
        return mid;
    }
};

也可以使用三个指针，分别表示应该由2或3或5乘以当前位置的丑数；

每次求一个丑数就是

1
dp\lbrack i\rbrack = min(2 \ast dp\lbrack p2\rbrack,3 \ast dp\lbrack p3\rbrack,5 \ast dp\lbrack p5\rbrack)

再把对应指针加一，再继续比较求下一个丑数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<long> dp(n + 1);
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i <= n; i++) {
            long d2 = dp[p2] * 2;
            long d3 = dp[p3] * 3;
            long d5 = dp[p5] * 5;
            dp[i] = min(d2, min(d3, d5));
            if (dp[i] == d2)
                p2++;
            if (dp[i] == d3)
                p3++;
            if (dp[i] == d5)
                p5++;
        }
        return dp[n - 1];
    }
};