剑指offer49 丑数【双指针】

题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。

示例:

1
2
3
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

  1. 1 是丑数。
  2. n 不超过1690。

解题思路

利用三个指针的方法,分别指向2,3,5的系数的位置,系数都为1开始,如果当前的数为系数于2,3,5的乘积,则系数右移一个数。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int nthUglyNumber(int n) {
if(n<=0){
return 0;
}
int[] dp=new int[n];
dp[0]=1;
int a=0;
int b=0;
int c=0;
for(int i=1;i<n;i++){
int num2=dp[a]*2;
int num3=dp[b]*3;
int num5=dp[c]*5;
int num=Math.min(num2,Math.min(num3,num5));
dp[i]=num;
if(num==num2){
a++;
}
if(num==num3){
b++;
}
if(num==num5){
c++;
}
}
return dp[n-1];
}
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(1)

资料

剑指offer49 丑数【双指针】

http://example.com/2021/05/28/剑指offer49-丑数/

Author

John Doe

Posted on

2021-05-28

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.