สมมติว่าเรามีตัวเลข n; เราต้องหาเลขน่าเกลียดตัวที่ n อย่างที่เราทราบกันดีว่าตัวเลขขี้เหร่คือตัวเลขเหล่านั้น ซึ่งมีตัวประกอบเฉพาะคือ 2, 3 และ 5 ดังนั้นถ้าเราต้องการหา 10 th จำนวนน่าเกลียด ผลลัพธ์จะเป็น 12 เนื่องจากตัวเลขที่น่าเกลียดสองสามตัวแรกคือ 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 เป็นต้น
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- กำหนดอาร์เรย์ v ขนาด (n + 1)
- ถ้า n เหมือนกับ 1 แล้ว:
- คืน 1
- สอง :=2, สาม :=3, ห้า :=5
- twoIdx :=2, threeIdx :=2, fiveIdx :=2
- สำหรับการเริ่มต้น i :=2 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ:
- curr :=ขั้นต่ำสอง สาม และห้า
- v[i] :=curr
- ถ้า curr เหมือนกับสอง ดังนั้น:
- สอง :=v[twoIdx] * 2;
- (เพิ่ม twoIdx โดย 1)
- ถ้าสกุลเงินเท่ากับสาม ดังนั้น:
- สาม :=v[threeIdx] * 3
- (เพิ่ม 3Idx โดย 1)
- ถ้าสกุลเงินเท่ากับห้า ดังนั้น:
- ห้า :=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
