超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。
题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
示例 1：
输入：n = 12, primes = [2,7,13,19]
输出：32
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
示例 2：输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。提示：
1 <= n <= 106
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据 保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ，且按 递增顺序 排列
在解这个题之前，我们需要对一些数学概念进行了解。
下面是百度百科的一些内容：
质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。除了1以外，两个没有其他共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。根据算术基本定理，任何正整数皆有独一无二的质因子分解式 [1] 。只有一个质因子的正整数为质数。
每个合数都可以写成几个质数（也可称为素数）相乘的形式 [2] ，这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数；而这个因数一定是一个质数。
我们举一些例子来看看：
1没有质因数(因为1不算质因数)
2的质因数是2(1*2，因为1不算质因数)
3的质因数是3
4的质因数是2(2*2)
5的质因数是5
6的质因数是2和3(2*3)
7的质因数是7
8的质因数是2(2* 2 *2)
9的质因数是3(3 * 3)
12的质因数是2和3(2* 2 *3)
理解了上面的这些概念，那我们应该可以理解这道题目了。
拿示例1来说，n = 12, primes = [2,7,13,19]
primes数组中的都是质因数，通过这些质因数来组成一个数(不限制质因数出现次数，因此会出现2、2 * 2、2* 2 *2)。
下面我们来具体看看这个丑数数组是怎么产生的：
首先丑数数组第一个值肯定是1，因为1没有质因数，因此其质因数肯定在primes数组中(这边有个需要理解的点，即没有的东西存在于任何东西中)。
丑数数组第二个值就是 2 ，第三个值是22(2 * 2 < 7)，第四个值是 7 ，第五个值是 2 2 *2，第六个值是 13，第七个值是2 * 7，第八个值是2 * 2 * 2 *2，第九个值是19，第十个值是2 * 13，第十一个值是2 * 2 * 7，第十二个值是 2 * 19，第十三个值是 2 * 2 * 13 ……
通过上面的枚举法感觉好像没看出有啥规律呀！！！
强行总结一下规律：
第一个值肯定是 primes数组中的第一个元素
第二个值有可能是 primes数组中的第二个元素，也有可能是primes数组中第一个元素的平方
第三个值有可能是primes数组中的第三个元素，也有可能是第一个元素的3次方，也有可能是第二个元素的平方
……
如果以这种思路去做的话，那后面的值太难找规律了，找不到规律编程也是很难的。
肯定有哪些规律我们没有找到！！！
发现自好像把数学问题和编程问题看成是一体的了，在上面我们讨论的数学问题中，其实最大的难点在于按照大小排序找出计算出这些丑数，在数学上看起来是没有啥规律的，但是在编程中其实是有解决办法的。
有时候觉得能把LeetCode题刷好的人真的挺厉害的，我自己感觉做LeetCode题就像高中做一些数学题的感觉，从数学的角度找到解决方法，然后用代码实现。因此刷题确实要好好静下心来刷，但是有时候也不完全是这样，数学上的解法不一定可以用代码实现，用数学的方法解决不了的也不一定不可以用代码实现。
了解数学的解法，代码的解法的边界以及适用范围需要在不断的做题过程中熟悉。
方法一：最小堆
要得到从小到大的第 nn 个超级丑数，可以使用最小堆实现。
初始时堆为空。首先将最小的超级丑数 11 加入堆。
每次取出堆顶元素 xx，则 xx 是堆中最小的超级丑数。对于数组 \textit{primes}primes 的任意质数 pp，pxpx 也是超级丑数，因此将数组 \textit{primes}primes 中的每个质数和 xx 的乘积分别加入堆。
上述做法会导致堆中出现重复元素的情况。为了避免重复元素，可以使用哈希集合去重，避免相同元素多次加入堆。
在排除重复元素的情况下，第 nn 次从最小堆中取出的元素即为第 nn 个超级丑数。
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
unordered_set<long> seen;
priority_queue<long, vector<long>, greater<long>> heap;
seen.insert(1);
heap.push(1);
int ugly = 0;
for (int i = 0; i < n; i++) {
long curr = heap.top();
heap.pop();
ugly = (int)curr;
for (int prime : primes) {
long next = curr * prime;
if (seen.insert(next).second) {
heap.push(next);
}
}
}
return ugly;
}
};
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
sort(primes.begin(), primes.end());
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(1);
int num = 0;
while(n > 0) {
int cur = pq.top(); pq.pop();
if(num == cur)
continue;
num = cur;
for(auto &prime : primes) {
if(cur <= INT_MAX / prime)
pq.push(num * prime);
else
break;
}
n--;
}
return num;
}
};
1.暴力 (brute force)
C++
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> v;
for (long long a=1;a<=INT_MAX;a=a*2)
for (long long b=a;b<=INT_MAX;b=b*3)
for (long long c=b;c<=INT_MAX;c=c*5)
v.push_back(c);
sort(v.begin(),v.end());
return v.at(n-1);
}
};
2、优先队列 (小顶堆)
优先队列/小顶堆/大顶堆
利用优先队列有自动排序的功能
每次取出队头元素，存入队头元素2、队头元素3、队头元素*5
但注意，像 12 这个元素，可由 4 乘 3 得到，也可由 6 乘 2 得到，所以要注意去重
C++
class Solution {
public:
int nthUglyNumber(int n) {
priority_queue <double,vector<double>,greater<double> > q;
double answer=1;
for (int i=1;i<n;++i)
{
q.push(answer*2);
q.push(answer*3);
q.push(answer*5);
answer=q.top();
q.pop();
while (!q.empty() && answer==q.top())
q.pop();
}
return answer;
}
};
还可以更进一步采用 set 来识别有无重复
C++
class Solution {
public:
int nthUglyNumber(int n) {
priority_queue <double,vector<double>,greater<double> > q;
set<int> s;
s.insert(1);
vector<int> mask({2,3,5});
double answer=1;
for (int i=1;i<n;++i)
{
for (int &j:mask)
if (s.count(answer*j)==0)
{
q.push(answer*j);
s.insert(answer*j);
}
answer=q.top();
q.pop();
}
return answer;
}
};
3.动态规划 (三指针)
我们先模拟手写丑数的过程
1 打头，1 乘 2 1 乘 3 1 乘 5，现在是 {1,2,3,5}
轮到 2，2 乘 2 2 乘 3 2 乘 5，现在是 {1,2,3,4,5,6,10}
手写的过程和采用小顶堆的方法很像，但是怎么做到提前排序呢
小顶堆的方法是先存再排，dp 的方法则是先排再存
我们设 3 个指针 p_2,p_3,p_5
代表的是第几个数的2倍、第几个数 3 倍、第几个数 5 倍
动态方程 dp[i]=min(dp[p_2]*2,dp[p_3]*3,dp[p_5]*5)
小顶堆是一个元素出来然后存 3 个元素
动态规划则是标识 3 个元素，通过比较他们的 2 倍、3 倍、5 倍的大小，来一个一个存
C++
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n);
dp.at(0)=1;
int p_2,p_3,p_5;
p_2=p_3=p_5=0;
for (int i=1;i<n;++i)
{
dp.at(i)=min(min(2*dp.at(p_2),3*dp.at(p_3)),5*dp.at(p_5));
if (dp.at(i)==2*dp.at(p_2))
++p_2;
if (dp.at(i)==3*dp.at(p_3))
++p_3;
if (dp.at(i)==5*dp.at(p_5))
++p_5;
}
return dp.at(n-1);
}
};