丑数（各种丑数题的变形版本）

【题目描述】

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

【解题思路】

研究丑数序列：

1 2 3 4 5 6 8 9 10 12 15

1 1*2 1*3 2*2 1*5 2*3 4*2 3*3 2*5 4*3

计算丑数：

1*2 1*3 1*5 min=1*2=2

2*2 1*3 1*5 min=1*3=3

2*2 2*3 1*5 min=2*2=4

……

【代码实现】（比较有难度，需要进一步消化）

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 class Solution {
 7 public:
 8     int GetUglyNumber_Solution(int index) {
 9         // 基本边界、基本参数
10         if (index <=0)
11             return 0;
12         vector<int> uglyNums(index, 1);
13         int idx2 = 0;
14         int idx3 = 0;
15         int idx5 = 0;
16         int idx = 1;
17 
18         //查找指定丑数
19         while (idx < index)
20         {
21             int uglyNumber = uglyNums[idx2] * 2<uglyNums[idx3] * 3 ? uglyNums[idx2] * 2 : uglyNums[idx3] * 3;
22             uglyNumber = uglyNumber<uglyNums[idx5] * 5 ? uglyNumber : uglyNums[idx5] * 5;
23             uglyNums[idx] = uglyNumber;
24             while (uglyNums[idx2]*2 <= uglyNums[idx])
25                 idx2++;
26             while (uglyNums[idx3]*3 <= uglyNums[idx])
27                 idx3++;
28             while (uglyNums[idx5]*5 <= uglyNums[idx])
29                 idx5++;
30             idx++;
31         }
32         return uglyNums[index - 1];
33     }
34 };
35 
36 
37 int main(void)
38 {
39     Solution *s = new Solution();
40     cout << s->GetUglyNumber_Solution(9) << endl;
41     system("pause");
42     return 0;
43 }

【举一反三】

1、判断一个数是否是丑数？

 1 bool isIgly(int num)
 2     {
 3         if (num<0)
 4             return false;
 5         if (num == 1)
 6             return true;
 7         while (num % 2 == 0)
 8             num /= 2;
 9         while (num % 3 == 0)
10             num /= 3;
11         while (num % 5 == 0)
12             num /= 5;
13 
14         if (num == 1)
15             return true;
16         else
17             return false;
18     }

2、找出第N个丑数？

 1  int GetUglyNumber_Solution(int index) {
 2         // 基本边界、基本参数
 3         if (index <=0)
 4             return 0;
 5         vector<int> uglyNums(index, 1);
 6         int idx2 = 0;
 7         int idx3 = 0;
 8         int idx5 = 0;
 9         int idx = 1;
10 
11         //查找指定丑数
12         while (idx < index)
13         {
14             int uglyNumber = uglyNums[idx2] * 2<uglyNums[idx3] * 3 ? uglyNums[idx2] * 2 : uglyNums[idx3] * 3;
15             uglyNumber = uglyNumber<uglyNums[idx5] * 5 ? uglyNumber : uglyNums[idx5] * 5;
16             uglyNums[idx] = uglyNumber;
17             while (uglyNums[idx2]*2 <= uglyNums[idx])
18                 idx2++;
19             while (uglyNums[idx3]*3 <= uglyNums[idx])
20                 idx3++;
21             while (uglyNums[idx5]*5 <= uglyNums[idx])
22                 idx5++;
23             idx++;
24         }
25         return uglyNums[index - 1];

3、找到number以内所有的丑数？

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 class Solution {
 7 public:
 8     void GetUglyNumUnderNumber(int number) {
 9         // 基本边界、基本参数
10         if (number <=0)
11             return;
12         vector<int> uglyNums(number,-1);//用以存放得到的丑数
13         uglyNums[0] = 1;
14         int idx2 = 0;
15         int idx3 = 0;
16         int idx5 = 0;
17         int idx = 1;
18 
19         //查找指定丑数
20         int uglyNumber = 1;
21         while (uglyNumber < number)
22         {
23             uglyNumber = uglyNums[idx2] * 2<uglyNums[idx3] * 3 ? uglyNums[idx2] * 2 : uglyNums[idx3] * 3;
24             uglyNumber = uglyNumber<uglyNums[idx5] * 5 ? uglyNumber : uglyNums[idx5] * 5;
25             uglyNums[idx] = uglyNumber;
26             while (uglyNums[idx2]*2 <= uglyNums[idx])
27                 idx2++;
28             while (uglyNums[idx3]*3 <= uglyNums[idx])
29                 idx3++;
30             while (uglyNums[idx5]*5 <= uglyNums[idx])
31                 idx5++;
32             idx++;
33         }
34 
35         //显示number以内所有的丑树
36         for (auto elem:uglyNums)
37         {
38             if (elem>-1)
39             {
40                 cout << elem << "	";
41             }
42         }
43         cout << endl;
44     }
45 };
46 
47 
48 int main(void)
49 {
50     Solution *s = new Solution();
51     s->GetUglyNumUnderNumber(9);
52     system("pause");
53     return 0;
54 }