【一些题】剑指offer：第k个丑数（还待i进一步优化）

本文主要是介绍【一些题】剑指offer：第k个丑数（还待i进一步优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

方法一程序：

long Ugly(int index);
bool IsUgly(long value);int main()
{clock_t clockbegin,clockend;clockbegin = clock();long result = Ugly(1500);clockend = clock();cout << clockend-clockbegin << endl;cout << result << endl;system("pause");return 0;
}long Ugly(int index)
{if(index < 1)return 0;int count = 1;int value = 1;while(count < index){++value;if(IsUgly(value)){++count;}}return value;
}bool IsUgly(long value)
{while(value%2 == 0)value/=2;while(value%3 == 0)value/=3;while(value%5 == 0)value/=5;return (value == 1)?true:false;
}

程序运行得很慢，得到结果如下（第一行是时间（ms），第二行是丑数）

****************************************************

采用方法二改进：方法一对每一个数都判断是否为丑数，方法2根据丑数之间的关系，只在原有丑数的基础上计算下一个丑数，程序如下：

int main()
{clock_t clockbegin,clockend;clockbegin = clock();long result = Ugly(1500);clockend = clock();cout << clockend-clockbegin << endl;cout << result << endl;system("pause");return 0;
}long Ugly(int index)
{if(index < 1)return 0;vector<long> ugly;ugly.reserve(index);ugly.push_back(1);  //第一个丑数int count = 1;while(count < index){int next_ugly;int M2 = 1, M3 = 1, M5 = 1;//找出第一个比当前最大丑数大的丑数for(int i = 0; M2 <= ugly[count-1]&& i < count; ++i){	M2 = ugly[i]*2; }for(int i = 0; M3 <= ugly[count-1]&& i < count; ++i){	M3 = ugly[i]*3; }for(int i = 0; M5 <= ugly[count-1]&& i < count; ++i){	M5 = ugly[i]*5; }next_ugly = min(min(M2, M3), M5);

<span style="white-space:pre">		</span>//将下一个丑数放入存储空间ugly.push_back(next_ugly);++count;}return ugly[index-1];
}

程序运行结果如下：

可见采用方法二，运行时间（590ms）相比方法一（88975ms）少了很多，直观感受上真是快了很多，感觉快的不行

*************************************************************************

继续按照方法三改进：方法二在找下一个丑数时，需要从头开始扫描，知道找到一个比当前丑数大的，而且对M2,M3,M5都要做这个工作；方法三对M2,M3,M5各保存一个扫描起点，在这个起点之前的点乘以2,3,5都不会比当前丑数大，因此只需从这个起点往后扫描。

程序如下：

long Ugly(int index)
{if(index < 1)return 0;vector<long> ugly;ugly.reserve(index);ugly.push_back(1);  //第一个丑数int count = 1;while(count < index){int next_ugly;int M2 = 1, M3 = 1, M5 = 1;int M2_begin = 0, M3_begin = 0, M5_begin = 0;//找出第一个比当前最大丑数大的丑数for(int i = M2_begin; M2 <= ugly[count-1]&& i < count; ++i){	M2 = ugly[i]*2; }for(int i = M3_begin; M3 <= ugly[count-1]&& i < count; ++i){	M3 = ugly[i]*3; }for(int i = M5_begin; M5 <= ugly[count-1]&& i < count; ++i){	M5 = ugly[i]*5; }//选出M2,M3,M5中最小的最为下一个丑数，同时将对应的起点+1next_ugly = min(min(M2, M3), M5);if(next_ugly == M2)++M2_begin;else if(next_ugly == M3)++M3_begin;else++M5_begin;//将下一个丑数存入存储空间中ugly.push_back(next_ugly);++count;}return ugly[index-1];
}

出乎意料的是，运行得时候没有感觉比程序二更飞起来的感觉，统计出的运行时间也确实和程序二差不多，实际上更慢了一点，结果如下：程序二（590ms）程序三（599ms）