【剑指offer】丑数 (含完整代码与注解)
1 引言
讲解两种解法：第一种为直接解法，VS中运行结果正确，但在“剑指offer”在线编程中报“程序超时或复杂性过大”错误；
第二种为以空间换时间解法，利用到库函数min，下面分别进行讲解，并附有完整代码与运行结果。
2 题目
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当
做是第一个丑数。求按从小到大的顺序的第N个丑数。
3 解法一：直接解法
附源代码与注解：
/**********************************************************
丑数的理解：如果一个数能被2整除，就连续除以2；如果能被3整除，
就连续除以3；如果能被5整除，就连续除以5；如果最后得到的是1，则
为丑数，否则不是
***********************************************************/
#include<iostream>
usingnamespace std;
bool uglyjudge(int num); //丑数判断函数声明
classSolution {
public:
int GetUglyNumber_Solution(intindex) {
int num = 0;
int isugly = 0;
while (isugly < index)
{
num++;
if (uglyjudge(num))
{
++isugly;
}
}
return num;
}
};
bool uglyjudge(intnum)//返回值为bool型，方便类Solution中if进行条件判断
{
while (num % 2 == 0)
num /= 2;
while (num % 3 == 0)
num /= 3;
while (num % 5 == 0)
num /= 5;
return (num == 1) ? true : false;
}
int main()
{
Solution s;
int x;
cout <<"输入一个数：";
while (cin >> x)
{
cout <<"第"<< x <<"个丑数为"<<s.GetUglyNumber_Solution(x)<<endl;
cout <<"输入一个数：";
}
return 0;
}
VS中运行结果为：剑指offer中运行结果为：
4 解法二： 空间换时间
4.1 min函数简单讲解
在头文件<algorithm>中， min(a, b);返回a、b中的较小者
注：min只能是两个变量中的较小的那个4.2 解题思路
将查找的丑数按从小到大的顺序排好序，注意每个丑数毕为前面的丑数乘以2、3或5得到的；把现有最大丑数记为M，则把第一个乘以2后大于M的结果记为M2，同理，把每个丑数乘以3和5 ，得到的第一个大于M的结果为M3和M5，那么下一个丑数必为M2/M3/M5这三个数的最小者。
4.3完整源代码
#include<iostream>
#include<algorithm>
#include<vector>
usingnamespace std;
classSolution {
public:
int GetUglyNumber_Solution(intindex) {
if (index< 7)
returnindex;
vector<int>num(index);
num[0] =1;
int t2= 0, t3 = 0, t5 = 0, i;
for (i= 1; i < index; ++i)
{
num[i] =min(num[t2] * 2, min(num[t3] * 3, num[t5] * 5)); //M2/M3/M5这三个数的最小者
if(num[i] == num[t2] * 2)t2++;
if(num[i] == num[t3] * 3)t3++;
if(num[i] == num[t5] * 5)t5++;
}
return num[index - 1];
}
};
int main()
{
Solution s;
int x;
cout <<"输入一个数：";
while (cin >> x)
{
cout <<"第"<< x <<"个丑数为"<<s.GetUglyNumber_Solution(x)<<endl;
cout <<"输入一个数：";
}
return 0;
}
在VS与剑指offer中均匀性正确，结果为：