資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告