用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

• 二：= 2，三：= 3，五：= 5

• twoIdx := 2, ThreeIdx := 2, FiveIdx := 2

• 对于初始化 i := 2，当 i <= n 时，更新（将 i 增加 1），执行：

• 五 := v[fiveIdx] * 5

• （将五个Idx增加1）

• 三 := v[threeIdx] * 3

• （将threeIdx增加1）

• 二：= v[twoIdx] * 2;

• （将 twoIdx 增加 1）

• curr := 最少两个、三个和五个

• v[i] := 当前

• 如果 curr 与两个相同，则：

• 如果 curr 与 3 相同，则：

• 如果 curr 与 5 相同，则：

• 返回 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