Leetcode.264丑数II

题目链接

Leetcode.264 丑数 II mid

题目描述

给你一个整数 n n n ，请你找出并返回第 n n n 个 丑数 。

丑数 就是质因子只包含 2 2 2、 3 3 3 和 5 5 5 的正整数。

示例1： 输入：n = 10 输出：12 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。 示例2： 输入：n = 1 输出：1 解释：1 通常被视为丑数。 提示: 1 ≤ n ≤ 1690 1 \leq n \leq 1690 1≤n≤1690 解法：动态规划

设 f ( n ) f(n) f(n) 代表第 n n n 个丑数。

因为每个丑数都只包含 2 , 3 , 5 2, 3, 5 2,3,5 的质因子(除开 1 1 1)，那么 f ( n ) f(n) f(n) 也就是第 n n n 个丑数，必然是由 [ 1 , n − 1 ] [1, n - 1] [1,n−1] 之间的某一个丑数，假设是 f ( i ) × 2 , f ( i ) × 3 , f ( i ) × 5 f(i) \times 2,f(i) \times 3, f(i) \times 5 f(i)×2,f(i)×3,f(i)×5，三个其中的一个而来。

很显然， f ( n ) f(n) f(n) 的值一定是 f ( i ) × 2 , f ( i ) × 3 , f ( i ) × 5 f(i) \times 2,f(i) \times 3, f(i) \times 5 f(i)×2,f(i)×3,f(i)×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 a, b, c a,b,c 分别代表 × 2 \times 2 ×2， × 3 \times 3 ×3， × 5 \times 5 ×5 代表的丑数。那么当前的丑数 f ( i ) f(i) 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}。

设 r 2 = f ( a ) × 2 r 3 = f ( b ) × 3 r 5 = f ( c ) × 5 r_2 = f(a) \times 2 \\ r_3 = f(b) \times 3 \\ r_5 = f(c) \times 5 r2​=f(a)×2r3​=f(b)×3r5​=f(c)×5

如果 f ( i ) = r 2 f(i) = r_2 f(i)=r2​，那么指针 a a a 就往后移动一位。

其原理是，如果 r 2 = f ( a ) × 2 r_2 = f(a) \times 2 r2​=f(a)×2 就是当前的第 i i i 个丑数，那么我们记录答案， f ( i ) = r 2 f(i) = r_2 f(i)=r2​。既然 f ( a ) × 2 f(a) \times2 f(a)×2 这个丑数已经在当前的答案集合 f f f 中了，那么比当前丑数 f ( a ) × 2 f(a) \times2 f(a)×2 更小的丑数也肯定在答案集合 f f f 中，所以后面只需要考虑比 f ( a ) × 2 f(a) \times 2 f(a)×2 更大的丑数，也就是 f ( a + 1 ) × 2 f(a+1) \times 2 f(a+1)×2，所以指针 a a a 才要往后移动一位。

对于 f ( i ) = r 3 f(i)=r_3 f(i)=r3​， f ( i ) = r 5 f(i) = r_5 f(i)=r5​ 的情况同理。

a , b , c a, b,c a,b,c 都初始化为 1 1 1， f ( 1 ) = 1 f(1) = 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 ) O(n) 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]; } };