Số II xấu xí trong C ++

Giả sử chúng ta phải tìm số xấu thứ n, vì vậy chúng ta phải xác định một phương pháp có thể tìm được nó. Như chúng ta biết rằng những số xấu xí là những số có thừa số nguyên tố chỉ là 2, 3 và 5. Vì vậy, nếu chúng ta muốn tìm số xấu thứ 10, đó sẽ là 12, vì một vài số xấu đầu tiên là 1, 2, 3, 4, 5, 6, 8, 9, 10, 12

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một mảng v, có kích thước n + 1

• nếu n =1, thì trả về 1

• hai:=2, ba =3 và năm =5, towIndex:=2, baIndex:=2 và nămIndex:=2

• cho tôi trong phạm vi từ 2 đến n

  • curr:=min của hai, ba và năm

  • v [i]:=curr

  • nếu curr =hai, thì hai:=v [twoIndex] * 2, tăng haiIndex thêm 1

  • nếu curr =ba, thì ba:=v [baIndex] * 3, tăng baIndex thêm 1

  • if curr =five, then five:=v [fiveIndex] * 3, tăng fiveIndex thêm 1

• trả về v [n]

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

10

Đầu ra

12