資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究C++ 中的醜數 II
假設我們要找到第 n 個醜數，那麼我們必須定義一種可以找到它的方法。我們知道醜數是指那些質因子僅為 2、3 和 5 的數字。因此，如果我們要找到第 10 個醜數，它將是 12，因為前幾個醜數是 1、2、3、4、5、6、8、9、10、12
為了解決這個問題，我們將遵循以下步驟：-
製作一個大小為 n + 1 的陣列 v
如果 n = 1，則返回 1
two := 2，three = 3 和 five = 5，towIndex := 2，threeIndex := 2 和 fiveIndex := 2
對於 2 到 n 範圍內的 i
curr := two、three 和 five 的最小值
v[i] := curr
如果 curr = two，則 two := v[twoIndex] * 2，將 twoIndex 增加 1
如果 curr = three，則 three := v[threeIndex] * 3，將 threeIndex 增加 1
如果 curr = five，則 five := v[fiveIndex] * 3，將 fiveIndex 增加 1
返回 v[n]
示例 (C++)
讓我們看看以下實現以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int nthUglyNumber(int n) {
vector <int> v(n + 1);
if(n == 1){
return 1;
}
int two = 2, three = 3, five = 5;
int twoIdx = 2;
int threeIdx = 2;
int fiveIdx = 2;
for(int i = 2; i <= n; i++){
int curr = min({two, three, five});
v[i] = curr;
if(curr == two){
two = v[twoIdx] * 2;;
twoIdx++;
}
if(curr == three){
three = v[threeIdx] * 3;
threeIdx++;
}
if(curr == five){
five = v[fiveIdx] * 5;
fiveIdx++;
}
}
return v[n];
}
};
main(){
Solution ob;
cout << (ob.nthUglyNumber(10));
}輸入
10
輸出
12
更新於： 02-May-2020
229 次瀏覽
廣告