題目鏈接

Leetcode.264 丑數 II mid

題目描述

給你一個整數 $n$ ，請你找出并返回第 $n$ 個 丑數 。

丑數 就是質因子只包含 $2$、$3$ 和 $5$ 的正整數。

示例1：

輸入：n = 10
輸出：12
解釋：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 個丑數組成的序列。

示例2：

輸入：n = 1
輸出：1
解釋：1 通常被視為丑數。

提示:

• $1\le n\le 1690$

解法：動態規劃

設 $f(n)$ 代表第 $n$ 個丑數。

因為每個丑數都只包含 $2,3,5$ 的質因子(除開 $1$)，那么 $f(n)$ 也就是第 $n$ 個丑數，必然是由 $[1,n?1]$ 之間的某一個丑數，假設是 $f(i)\times 2,f(i)\times 3,f(i)\times 5$，三個其中的一個而來。

很顯然，$f(n)$ 的值一定是 $f(i)\times 2,f(i)\times 3,f(i)\times 5$ 三者之中的最小值。

舉例說明：

f(1) = 1
f(2) = f(1) * 2 = 2
f(3) = f(1) * 3 = 3
f(4) = f(2) * 2 = 4
f(5) = f(1) * 5 = 5
f(6) = f(3) * 2 = 6
f(7) = f(4) * 2 = 8
f(8) = f(3) * 3 = 9

我們用三個指針 $a,b,c$ 分別代表 $\times 2$， $\times 3$， $\times 5$ 代表的丑數。那么當前的丑數 $f(i)$ 就是 m i n { f ( a ) × 2 , f ( b ) × 3 , f ( c ) × 5 } min\{ f(a) \times 2, f(b) \times 3, f(c) \times 5\} min{f(a)×2,f(b)×3,f(c)×5}。

設
$$\begin{gathered} r_2=f(a)\times 2 \\ {r}_3=f(b)\times 3 \\ {r}_5=f(c)\times 5 \end{gathered}$$

如果 $f(i)=r_2$，那么指針 $a$ 就往后移動一位。

其原理是，如果 $r_2=f(a)\times 2$ 就是當前的第 $i$ 個丑數，那么我們記錄答案，$f(i)=r_2$。既然 $f(a)\times 2$ 這個丑數已經在當前的答案集合 $f$ 中了，那么比當前丑數 $f(a)\times 2$ 更小的丑數也肯定在答案集合 $f$ 中，所以后面只需要考慮比 $f(a)\times 2$ 更大的丑數，也就是 $f(a+1)\times 2$，所以指針 $a$ 才要往后移動一位。

對于 $f(i)=r_3$，$f(i)=r_5$ 的情況同理。

$a,b,c$ 都初始化為 $1$，$f(1)=1$。

{ r 2 = f ( a ) × 2 r 3 = f ( b ) × 3 r 5 = f ( c ) × 5 f ( i ) = m i n { r 2 , r 3 , r 5 } , i ∈ [ 2 , n ] i f r 2 = f ( i ) t h e n a + 1 i f r 3 = f ( i ) t h e n b + 1 i f r 5 = f ( i ) t h e n c + 1 \left\{\begin{array}{l} r_2 = f(a) \times 2 \\ r_3 = f(b) \times 3 \\ r_5 = f(c) \times 5 \\ f(i) = min\{r_2, r_3,r_5\},\ i \in [2,n]\\ if\ r_2=f(i) \ then \ a + 1 \\ if\ r_3=f(i) \ then \ b + 1 \\ if\ r_5=f(i) \ then \ c + 1 \end{array}\right. ? ? ??r2?=f(a)×2r3?=f(b)×3r5?=f(c)×5f(i)=min{r2?,r3?,r5?},?i∈[2,n]if?r2?=f(i)?then?a+1if?r3?=f(i)?then?b+1if?r5?=f(i)?then?c+1?

時間復雜度：$O(n)$

C++：

class Solution {
public:int nthUglyNumber(int n) {vector<int> f(n + 1);f[1] = 1;int a = 1, b = 1, c = 1;for(int i = 2; i <= n; ++i){int r2 = f[a] * 2, r3 = f[b] * 3, r5 = f[c] * 5;f[i] = min({r2, r3, r5});if(f[i] == r2) a++;if(f[i] == r3) b++;if(f[i] == r5) c++;}return f[n];}
};