• 操作系統：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