根据丑数定义，能写成2/3/5乘积的数即为丑数，按照此原理写下面代码，但是算法时间复杂度过高。 改进1：增加长度为1000的辅助数组，如果将数分解到1000以内的时候，直接判断是否是丑数，但是运行时间好像没啥变化，尝试失败。
/** *Copyright @ 2019 Zhang Peng. All Right Reserved. *Filename: *Author: Zhang Peng *Date: *Version: *Description:剑指offer 面试题49 丑数 **/ #include<iostream> #include<ctime> using namespace std; class Solution { private: const int maxlen = 10; public: bool isUglynum(int num, int * record) { int temp = num; /*if(record[temp]!=-1) return (bool)record[temp];*/ while (temp % 2 == 0) { temp /= 2; if (num <= maxlen&&record[temp] != -1) { record[num] = record[temp]; return (bool)record[temp]; } } while (temp % 3 == 0) { temp /= 3; if (num <= maxlen&&record[temp] != -1) { record[num] = record[temp]; return (bool)record[temp]; } } while (temp % 5 ==0) { temp /= 5; if (num <= maxlen&&record[temp] != -1) { record[num] = record[temp]; return (bool)record[temp]; } } bool result_final; if (temp == 1) { result_final = true; if (num <= maxlen) { record[num] = 1; } } else { result_final = false; if (num <= maxlen) { record[num] = 0; } } return result_final; } int GetUglyNumber_Solution(int index) { if (index <= 0) return 0; int i = 1; int * record=new int[maxlen]; for (int k = 0; k<maxlen; k++) record[k] = -1; record[1] = 1; if (index == 1) return 1; else { int count = 1; while (count != index) { i++; if (isUglynum(i, record)) { cout << i << " "; count++; } } } return i; } }; int main() { Solution s; clock_t start, finish; start = clock(); int num = s.GetUglyNumber_Solution(1500); cout << endl; cout << num << endl; finish = clock(); cout << "consume time: " << finish - start << "ms" << endl; system("pause"); return 0; }图中单位有误，应为ms 改进2：上述思路主要是需要判断每一个数是否是丑数，如果我们可以生成每一个丑数，则不用判断那么多次，别的博客中称这一思路为构造法。
/** *Copyright @ 2019 Zhang Peng. All Right Reserved. *Filename: *Author: Zhang Peng *Date: *Version: *Description:剑指offer 面试题49 丑数 **/ #include<iostream> #include<ctime> using namespace std; class Solution { public: int Min(int x1, int x2, int x3) { int temp = (x1<x2) ? x1 : x2; return (temp<x3) ? temp : x3; } int GetUglyNumber_Solution(int index) { if (index <= 0) return 0; int * result = new int[index]; result[0] = 1; int nextindex = 1; int * point2 = result; int * point3 = result; int * point5 = result; while (nextindex<index) { int minvalue = Min((*point2) * 2, (*point3) * 3, (*point5) * 5); result[nextindex] = minvalue; cout << result[nextindex] << " "; while ((*point2) * 2 <= result[nextindex]) point2++; while ((*point3) * 3 <= result[nextindex]) point3++; while ((*point5) * 5 <= result[nextindex]) point5++; nextindex++; } int result_final = result[nextindex - 1]; delete[] result; return result_final; } }; int main() { Solution s; clock_t start, finish; start = clock(); int num = s.GetUglyNumber_Solution(1500); cout << endl; cout << num << endl; finish = clock(); cout << "consume time: " << finish - start << "ms" << endl; system("pause"); return 0; }结果如图： 两者速度上相差几十倍，这就是算法的力量。
