【IT笔试面试题整理】丑数

【试题描述】我们把只包含因子2、3和5的数称作丑数。求按从到大的顺序的第1500个丑数。例如6,8是丑数,而14不是,因为它包含因子7.习惯上把1当作第一个丑数。

【试题来源】未知

【参考代码】

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
int Min(int a, int b, int c) {

return (a < b ? a : b) < c ? (a < b ? a : b) : c;
}

int uglyNumber(int n) {

if(n <= 0) {
throw ("Invalid Input.");
}

long* uglyNum = new long[n];
uglyNum[0] = 1;

int index2 = 0;
int index3 = 0;
int index5 = 0;
int indexLast = 0;

while(indexLast < n) {
int min = Min(uglyNum[index2] * 2, uglyNum[index3] * 3, uglyNum[index5] * 5);
uglyNum[++indexLast] = min;

while(uglyNum[index2] * 2 <= uglyNum[indexLast]) {
index2++;
}

while(uglyNum[index3] * 3 <= uglyNum[indexLast]) {
index3++;
}

while(uglyNum[index5] * 5 <= uglyNum[indexLast]) {
index5++;
}
}

return uglyNum[n - 1];

}
坚持原创技术分享,您的支持将鼓励我继续创作!