数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中的超级丑数
我们需要创建一个函数来查找第 n 个超级丑数。超级丑数是所有质因数都在给定质数列表 primes（大小为 k）中的正数。所以如果 n 是 12 并且 primes 是 [2, 7, 13, 19]，那么输出将是 32，这是因为 [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] 是 12 个超级丑数的序列。
为了解决这个问题，我们将遵循以下步骤：
创建一个数据结构三元组，包含 num、prime 和 idx
如果 n 是 1，则返回 1，创建一个大小为 n + 1 的数组，并用 1 填充它
定义一个优先级队列 pq
对于范围 0 到 primes 大小：
创建三元组 t(primes[i], primes[i], 2)
对于范围 2 到 n
curr := pq 的顶部元素，然后从 pq 中删除
val := curr 的 num
v[i] := val
curr 的 num := curr 的 prime * v[curr 的 index]
将 curr 的 index 加 1
将 curr 插入 pq
当 val = pq 顶部的 num 时：
curr := pq 的顶部并从 pq 中删除
curr 的 num := curr 的 prime * v[curr 的 index]
将 curr 的 index 加 1
将 curr 插入 pq
返回 v[n]
示例 (C++)
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
struct Data{
int num, prime, idx;
Data(int a, int b, int c){
num = a;
prime = b;
idx = c;
}
};
struct Comparator{
bool operator()(Data a, Data b){
return !(a.num < b.num);
}
};
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
if(n == 1)return 1;
vector <int> v(n + 1, 1);
priority_queue < Data, vector < Data >, Comparator > pq;
for(int i = 0; i < primes.size(); i++){
pq.push(Data(primes[i], primes[i], 2));
}
int x;
for(int i = 2; i <= n; i++){
Data curr = pq.top();
pq.pop();
int val = curr.num;
v[i] = val;
curr.num = curr.prime * v[curr.idx];
curr.idx++;
pq.push(curr);
while(val == pq.top().num){
curr = pq.top();
pq.pop();
curr.num = curr.prime * v[curr.idx];
curr.idx++;
pq.push(curr);
}
}
return v[n];
}
};
main(){
Solution ob;
vector<int> v = {2,7,13,19};
cout << (ob.nthSuperUglyNumber(12, v));
}输入
12 [2,7,13,19]
输出
32
更新于: 2020-04-29
265 次查看
广告