-
Notifications
You must be signed in to change notification settings - Fork 44
/
ugly_number.cpp
117 lines (96 loc) · 2.64 KB
/
ugly_number.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/*
* Copyright(c) 2019 Jiau Zhang
* For more information see <https://github.com/JiauZhang/algorithms>
*
* This repo is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation
*
* It is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with THIS repo. If not, see <http://www.gnu.org/licenses/>.
*/
#include <iostream>
using namespace std;
bool isUglyNumber(int num)
{
while (num%2 == 0)
num /= 2;
while (num%3 == 0)
num /= 3;
while (num%5 == 0)
num /= 5;
//cout << "num = " << num << endl;
return (num == 1) ? true : false;
}
void Test(int num)
{
//从输出可以看出,这句代码先执行函数isUglyNumber
cout << "number = " << num << "-->" \
<< "is ugly: " << isUglyNumber(num) << endl;
}
int getUglyNumber(int index)
{
if (index <= 0)
return -1;
int count = 0;
int num = 0;
while (count < index) {
++num;
if (isUglyNumber(num))
count++;
}
return num;
}
int min(int num1, int num2, int num3)
{
int temp = (num1 > num2) ? num2 : num1;
temp = (temp < num3) ? temp : num3;
return temp;
}
//此方法速度比较快,但是浪费内存,用空间换时间
int _getUglyNumber_(int index)
{
if (index <= 0)
return -1;
int *ugly_numbers = new int[index];
int *f2 = ugly_numbers;
int *f3 = ugly_numbers;
int *f5 = ugly_numbers;
ugly_numbers[0] = 1;
int next_ugly_number = 1;
while (next_ugly_number < index) {
ugly_numbers[next_ugly_number] = min(*f2*2, *f3*3, *f5*5);
while (*f2*2 <= ugly_numbers[next_ugly_number])
f2++;
while (*f3*3 <= ugly_numbers[next_ugly_number])
f3++;
while (*f5*5 <= ugly_numbers[next_ugly_number])
f5++;
next_ugly_number++;
}
delete[] ugly_numbers;
return ugly_numbers[index-1];
}
int main(int argc, char **argv)
{
int numbers[5] = {5, 15, 26, 30, 49};
Test(numbers[0]);
Test(numbers[1]);
Test(numbers[2]);
Test(numbers[3]);
Test(numbers[4]);
int num_idx = getUglyNumber(5);
cout << "getUglyNumber num_idx: " << num_idx << endl;
num_idx = _getUglyNumber_(5);
cout << "_getUglyNumber_ num_idx: " << num_idx << endl;
num_idx = getUglyNumber(25);
cout << "getUglyNumber num_idx: " << num_idx << endl;
num_idx = _getUglyNumber_(25);
cout << "_getUglyNumber_ num_idx: " << num_idx << endl;
return 0;
}