//题目：丑数，我们把只包含因子2，3，5的数称为偶数，按从下到大第1500个丑数。
//解法1：逐个判段每个数是否是丑数
public class Main {
public static void main(String[] args) throws Exception {
System.out.println(findUglyNumber(100));
}
public static int findUglyNumber(int n){
int result = 1;
int num = 2;
while(result<n){
if(isUgly(num)){
result++;
}
num++;
}
return num-1;
}
public static boolean isUgly(int num){
while(num % 2 == 0){
num = num/2;
}
while(num % 3 == 0){
num = num/3;
}
while(num % 5 == 0){
num = num/5;
}
if(num == 1){
return true;
}else{
return false;
}
}
}
//解法2：逐个计算下一个丑数的值,并将其保存在数组中，使用三个下标分别代表2，3，5的情况
public class Main {
public static void main(String[] args) throws Exception {
System.out.println(findUglyNumber(1500));
}
public static int findUglyNumber(int n){
if(n<=0){
return 0;
}
int[] number = new int[n];
int index = 0;
number[index] = 1;
index++;
int index2 = 0; //使用三个index来标记2,3,5
int index3 = 0;
int index5 = 0;
while(index<n){
number[index] = getMin(number[index2]*2,number[index3]*3,number[index5]*5);
while(number[index]>=number[index2]*2){ //更新三个标签的值
index2++;
}
while(number[index]>=number[index3]*3){
index3++;
}
while(number[index]>=number[index5]*5){
index5++;
}
index++;
}
return number[index-1];
}
public static int getMin(int num1, int num2, int num3){ //取三个值中的最小值
int result = num1;
if(result>num2){
result = num2;
}
if(result>num3){
result = num3;
}
return result;
}
}
