剑指offer系列26：丑数

z剑指offer这一章都是这种题型，求优化解的，尽可能降低算法的复杂度。这个题不难，首先要想清楚什么是丑数，其次，想清楚如何生成丑数。还有，如何表达生成的丑数。这个题在表达丑数的构成上的代码很巧妙。

 1 #include<iostream>
 2 #include<string>
 3 #include <vector>
 4 #include <algorithm>
 5 //#include <sstream>
 6 using namespace std;
 7 class Solution {
 8 public:
 9     int ugly[1000];
10     int minOlivia(int a, int b, int c)
11     {
12         int temp = (a < b) ? a : b;
13         return (temp < c) ? temp : c;
14     }
15     int GetUglyNumber_Solution(int index) {
16         if (index == 0)
17             return 0;
18         ugly[0] = 1;
19         int index2 = 0;
20         int index3 = 0;
21         int index5 = 0;
22         int n = 1;
23         int val=1;
24         while (n < index)
25         {
26             val = minOlivia(ugly[index2] * 2, ugly[index3] * 3, ugly[index5] * 5);
27             if (val == ugly[index2] * 2)
28                 index2++;
29             if (val == ugly[index3] * 3)
30                 index3++;
31             if (val == ugly[index5] * 5)
32                 index5++;
33             ugly[n] = val;
34             n++;
35         }
36         int re = ugly[n - 1];
37         return re;
38 
39     }
40 };
41 int main()
42 {
43     Solution so;
44     //vector<int> test{ 3,5,1,4,2 };
45     cout << so.GetUglyNumber_Solution(10) << endl;
46     return 0;
47 }