时间复杂度：以空间来换取时间

题目：

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

法1，

复杂度较高，就是从1一直往上累加，每个数判断一下是不是丑数：

#include <iostream> #include <ctime> #include <vector> using namespace std; class Solution { public: int GetUglyNumber_Solution(int index) { if(index <= 0){ return 0; } if(index == 1) return 1; int num = 1; while(num){ if(IsUgly(num)) index --; if(index == 0) break; num++; } return num; } //判断一个给定的数是不是丑数； bool IsUgly(int n){ while(n%2 == 0) n = n / 2; while(n % 3 == 0) n = n / 3; while(n % 5 == 0) n = n / 5; return (n == 1) ? 1 : 0; } }; int main() { clock_t start, finish; double totaltime; start= clock(); Solution s; int temp = s.GetUglyNumber_Solution(1500); cout << temp << endl; finish = clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"\n此程序的运行时间为"<<totaltime<<"秒！"<<endl; return 0; }

输出如下：

859963392 此程序的运行时间为14.982秒！

法2、

#include <iostream> #include <ctime> #include <vector> using namespace std; class Solution { public: int GetUglyNumber_Solution(int index) { if(index <= 0) return 0; if(index == 1) return 1; vector<int> ugly_num; ugly_num.push_back(1); int index_2 = 0; int temp_2 = 0; int index_3 = 0; int temp_3 = 0; int index_5 = 0; int temp_5 = 0; while(ugly_num.size() != index){ for( ; index_2 < ugly_num.size(); index_2++){ //cout << ugly_num[index_2] << endl; temp_2 = 2 * ugly_num[index_2]; if(temp_2 > ugly_num.back()) break; } for( ; index_3 < ugly_num.size(); index_3++){ temp_3 = 3 * ugly_num[index_3]; if(temp_3 > ugly_num.back()) break; } for( ; index_5 < ugly_num.size(); index_5++){ temp_5 = 5 * ugly_num[index_5]; if(temp_5 > ugly_num.back()) break; } int min = temp_2 >= temp_3 ? temp_3 : temp_2; min = min >= temp_5 ? temp_5 : min; ugly_num.push_back(min); } return ugly_num.back(); } }; int main() { clock_t start, finish; double totaltime; start= clock(); Solution s; int temp = s.GetUglyNumber_Solution(1500); cout << temp << endl; finish = clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"\n此程序的运行时间为"<<totaltime<<"秒！"<<endl; return 0; }

输出如下：

859963392 此程序的运行时间为0.001秒！

可以看到法2运行的时间远远小于法1，但是代价是法2需要建立一个vector数组，把从1到index的丑数都存储起来，以空间来换取时间。