資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式查詢第n個醜數
假設我們有一個數字n；我們需要找到第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
- twoIdx := 2，threeIdx := 2，fiveIdx := 2
- 從i := 2開始，當i <= n時，更新（i增加1），執行以下操作：
- curr := two、three和five中的最小值
- v[i] := curr
- 如果curr等於two，則
- two := v[twoIdx] * 2;
- (twoIdx增加1)
- 如果curr等於three，則
- three := v[threeIdx] * 3
- (threeIdx增加1)
- 如果curr等於five，則
- five := v[fiveIdx] * 5
- (fiveIdx增加1)
- 返回v[n]
讓我們看看下面的實現，以便更好地理解
示例
#include
using namespace std;
class Solution {
public:
int nthUglyNumber(int n) {
vector 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(15));
}輸入
15
輸出
24
更新於: 2020年11月26日
255 次檢視
廣告