本文为剑指 offer 系列第三十二篇。
主要知识点为枚举。两种解题方法：一种是暴力枚举，一种是比较优美的枚举。
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
解题思路
思路1
从1开始计数，依次的判断每个数字是不是丑数，给丑数建立一个计数器，如果计数器为N,则返回这个结果。
思路2
因为丑数的质因子只有2.3.5三个数字，那么我们依次的去找他们之间乘积的最小值即可（可能每次每个数字乘的次数不一样，但是依旧是找最小的）。
解题代码
思路1代码
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
| class Solution {
public:
int GetUglyNumber_Solution(int index) {
int count = 1;
int temp = 1;
while(count < index){
if(isUglyNumber(++temp)){
count++;
}
}
return temp;
}
bool isUglyNumber(int num){
while(num%5 == 0){
num /= 5;
}
while(num%3 == 0){
num /= 3;
}
while(num%2 == 0){
num /= 2;
}
return num == 1?true:false;
}
};
|
时间复杂度为O(nlgn),空间复杂度为O(1)，非常意料之内的在牛客上超时了。
思路2代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int GetUglyNumber_Solution(int index) {
vector<int> res ={1};
int p2 = 0,p3 = 0,p5 = 0;
int temp = 0;
for(int i = 1;i<index;i++){
temp = min(res[p2]*2,min(res[p5]*5,res[p3]*3));
res.push_back(temp);
if(temp == res[p2]*2) p2++;
if(temp == res[p3]*3) p3++;
if(temp == res[p5]*5) p5++;
}
return res[index-1];
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
思路1测试代码
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
30
31
32
| /*test.cpp*/
#include <iostream>
using namespace std;
bool isUglyNumber(int num){
while(num%5 == 0){
num /= 5;
}
while(num%3 == 0){
num /= 3;
}
while(num%2 == 0){
num /= 2;
}
return num == 1?true:false;
}
int GetUglyNumber_Solution(int index) {
int count = 1;
int temp = 1;
while(count < index){
if(isUglyNumber(++temp)){
count++;
}
}
return temp;
}
int main(){
cout<< GetUglyNumber_Solution(1400)<<endl;
}
|
调用的时候
1
2
| g++ test.cpp -o test
./test
|
结果是516560652.答案正确。
除了运算的慢点，所需要的时间长点，其他没啥毛病。
以上，本题结束！