C++面试题（35）-------找出第 n 个丑数（Ugly Number）

• 操作系统：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;  // 第一个丑数是1

        int 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;  // 输出 12
    cout <<"第1个丑数:"<< sol.nthUglyNumber( 1 ) << endl;   // 输出 1
    cout << "第15个丑数:"<<sol.nthUglyNumber( 15 ) << endl;  // 输出 24
    return 0;
}

运行结果

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