丑数

Desicription

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
long long GetUglyNumber_Solution(int index) {
if(index == 0) {
return 0;
}
set<long long> s;
int token = 0;
s.insert(1);
while(token + 1 < index) {
auto currentPoint = s.begin();
long long currentNumber = *currentPoint;
s.erase(currentPoint);
token++;
s.insert(currentNumber * 2);
s.insert(currentNumber * 3);
s.insert(currentNumber * 5);
}
return *s.begin();
}
};