定义:我们把只包含因子2、3和5的数称作丑数(Ugly Number)。
求按从小到大的顺序的第1500个丑数。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做第一个丑数。
1,一遍遍历法-效率比较低
-
如果一个数能够被2整除,那么让他继续除以2;
-
如果一个数能够被3整除,那么让他继续除以3;
-
如果一个数能够被5整除,那么让他继续除以5;
-
如果最后这个数变为1,那么这个数就是丑数,否则不是。
--
public static int getUglyNumber(int index) {
int number = 0;
for (int i = 0; i < index; i++) {
if(isUgly(i)) {
number = i;
break;
}
}
return number;
}
public static boolean isUgly(int number) {
while (number % 2 == 0) {
number = number / 2;
}
while (number % 3 == 0) {
number = number / 3;
}
while (number % 5 == 0) {
number = number / 5;
}
return number == 1;
}
2,空间换时间法:时间效率较高
- 根据丑数的定义,我们可以知道丑数可以由另外一个丑数乘以2,3或者5得到。
- 因此我们可以创建一个数组,里面的数字是排好序的丑数,每一个丑数都是前面的丑数乘以2,3或者5得到的。
网友评论