• 操作系统：ubuntu22.04
• IDE:Visual Studio Code
• 编程语言：C++11

题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
请编写一个函数，找出第 n 个丑数。

示例：

输入: n = 10
输出: 12
解释: 第10个丑数是12

解法思路：动态规划 + 三指针

这是一道典型的动态规划问题，也可以用最小堆来解，但最优解是使用 三指针法，时间复杂度为 O(n)，空间复杂度为 O(n)。
思路详解：

我们要构造一个丑数数组 dp[]，其中 dp[i] 表示第 i 个丑数。

每个新的丑数只能由之前的丑数乘以 2、3 或 5 得到。

我们维护三个指针：

• i2：指向下一个将乘以 2 的位置；
• i3：指向下一个将乘以 3 的位置；
• i5：指向下一个将乘以 5 的位置；

每次取这三个候选值中的最小值作为下一个丑数，并移动对应指针

代码实现

#include <vector>using namespace std;class Solution {
public:int nthUglyNumber( int n ){vector< int > dp( n );dp[ 0 ] = 1;  // 第一个丑数是1int i2 = 0, i3 = 0, i5 = 0;for ( int i = 1; i < n; ++i ){int next2 = dp[ i2 ] * 2;int next3 = dp[ i3 ] * 3;int next5 = dp[ i5 ] * 5;int nextUgly = min( next2, min( next3, next5 ) );dp[ i ]      = nextUgly;if ( nextUgly == next2 )i2++;if ( nextUgly == next3 )i3++;if ( nextUgly == next5 )i5++;}return dp[ n - 1 ];}
};#include <iostream>int main()
{Solution sol;cout <<"第10个丑数:"<< sol.nthUglyNumber( 10 ) << endl;  // 输出 12cout <<"第1个丑数:"<< sol.nthUglyNumber( 1 ) << endl;   // 输出 1cout << "第15个丑数:"<<sol.nthUglyNumber( 15 ) << endl;  // 输出 24return 0;
}

运行结果

第10个丑数:12
第1个丑数:1
第15个丑数:24