题目描述
把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
import java.util.ArrayList;
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index<=0){
return 0;
}else if(index==1){
return 1;
}
int p2=0;
int p3=0;
int p5=0;
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
for(int m=2; m<=index; m++){
int i = 2*list.get(p2);
int j = 3*list.get(p3);
int k = 5*list.get(p5);
if(i==minNum(i,j,k)){
p2++;
list.add(i);
}
if(j==minNum(i,j,k)){
p3++;
//如果之前已经添加过,则不再重复添加
if(list.size()!=m){
list.add(j);
}
}
if(k==minNum(i,j,k)){
p5++;
//如果之前已经添加过,则不再重复添加
if(list.size()!=m){
list.add(k);
}
}
}
return list.get(index-1);
}
public int minNum(int i, int j, int k){
int tmp = minNum(i,j);
return minNum(tmp,k);
}
public int minNum(int i, int j){
if(i<=j){
return i;
}else{
return j;
}
}
}