如何拥有自己的网站,网络规划与设计案例,建设网站 备案,网络推广培训学费几万题目链接 Leetcode.264 丑数 II mid 题目描述
给你一个整数 n n n #xff0c;请你找出并返回第 n n n 个 丑数 。
丑数 就是质因子只包含 2 2 2、 3 3 3 和 5 5 5 的正整数。
示例1#xff1a;
输入#xff1a;n 10
输出#xff1a;12
解释#xff1a;[1, 2, 3,…题目链接 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 r2f(a)×2r3f(b)×3r5f(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 r2f(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(a1) \times 2 f(a1)×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_2f(i) \ then \ a 1 \\ if\ r_3f(i) \ then \ b 1 \\ if\ r_5f(i) \ then \ c 1 \end{array}\right. ⎩ ⎨ ⎧r2f(a)×2r3f(b)×3r5f(c)×5f(i)min{r2,r3,r5}, i∈[2,n]if r2f(i) then a1if r3f(i) then b1if r5f(i) then c1
时间复杂度 O ( n ) O(n) O(n)
C
class Solution {
public:int nthUglyNumber(int n) {vectorint 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];}
};
