สมมติว่าเราต้องหาเลขน่าเกลียดตัวที่ n ดังนั้นเราต้องกำหนดวิธีที่จะหาได้ อย่างที่เราทราบดีว่าเลขขี้เหร่คือตัวเลขเหล่านั้น ซึ่งตัวประกอบเฉพาะคือ 2, 3 และ 5 ดังนั้นถ้าเราต้องการหาเลขขี้เหร่ตัวที่ 10 มันจะเป็น 12 เนื่องจากจำนวนที่น่าเกลียดสองสามตัวแรกคือ 1, 2, 3 4, 5, 6, 8, 9, 10, 12
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างอาร์เรย์ v ขนาด n + 1
-
ถ้า n =1 ให้คืนค่า 1
-
สอง :=2, สาม =3 และห้า =5, towIndex :=2, threeIndex :=2 และ fiveIndex :=2
-
สำหรับฉันอยู่ในช่วง 2 ถึง n
-
curr :=นาทีของสอง, สามและห้า
-
v[i] :=curr
-
ถ้า curr =สอง ดังนั้น two :=v[twoIndex] * 2 ให้เพิ่ม twoIndex ขึ้น 1
-
ถ้า curr =สาม ดังนั้นสาม :=v[threeIndex] * 3 ให้เพิ่ม threeIndex ขึ้น 1
-
ถ้าสกุลเงิน =ห้า ดังนั้นห้า :=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
