题目描述
我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做第一个丑数。
解题思路
.如果一个数能够被2整除，那么让他继续除以2；如果一个数能够被3整除，那么让他继续除以3；如果一个数能够被5整除，那么让他继续除以5；如果最后这个数变为1，那么这个数就是丑数，否则不是。
算法图解
优化：选定第一个丑数1，根据丑数的定义，可知以后的丑数必然是在1的基础上乘以2，乘以3，乘以5，因此可以得出三个丑数，从中选择最小的一个添加到list列表中，之后若list中的丑数与得出的三个丑数中的一个或两个相等，将对应的下标后移。
参考代码：
package offer
;
public class Offer49 {
public static void main(String
[] args
) {
System
.out
.println(getAllNumber(1500));
}
static boolean isUglyNumber(int num
) {
while (num
% 2 == 0) {
num
= num
>> 1;
}
while (num
% 3 == 0) {
num
= num
/ 3;
}
while (num
% 5 == 0) {
num
= num
/ 5;
}
return (num
== 1) ? true : false;
}
static int getAllNumber(int num
) {
if (num
<= 0) {
return 0;
}
int number
= 0;
int ugly
= 0;
while (ugly
< num
) {
number
++;
if (isUglyNumber(number
)) {
ugly
++;
}
}
return number
;
}
}
import java
.util
.*
;
public class Solution {
public int GetUglyNumber_Solution(int index
) {
if(index
<=0){
return 0;
}
ArrayList
<Integer> list
=new ArrayList<>();
list
.add(1);
int t2
=0,t3
=0,t5
=0;
while(list
.size()<index
){
int m2
=list
.get(t2
)*2;
int m3
=list
.get(t3
)*3;
int m5
=list
.get(t5
)*5;
int min
=Math
.min(m2
,Math
.min(m3
,m5
));
list
.add(min
);
if(min
==m2
){
t2
++;
}
if(min
==m3
){
t3
++;
}
if(min
==m5
){
t5
++;
}
}
return list
.get(list
.size()-1);
}
}
附录
该题源码在我的 ?Github 上面！
