第49题 丑数
题目 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数（剑指offer上明确规定是第1500个丑数，这里没有限制丑数范围）。
剑指offer的思路
- 逐个判断每个整数是不是丑数的解法，直观但不够高效，由于没有限制丑数范围的话，这种方法很容易超时，实时上我的确超时了；
public class Solution {
public int GetUglyNumber_Solution(int index) {
//按照思路写的，已经超时，所以正确性没有完全得到验证；
/* if(index<=0) {
return 0;
}
int num = 1;
int count = 1;
while (count != index) {
num++;
int temp = num;
boolean flag = false;
while (temp % 2 == 0 || temp % 3 == 0 || temp % 5 == 0) {
if (temp % 2 == 0) {
temp = temp / 2;
} else if (temp % 3 == 0) {
temp = temp / 3;
} else if (temp % 5 == 0) {
temp = temp / 5;
}
if (temp == 1) {
flag = true;
break;
}
}
if (flag) {
count++;
}
}
return num;*/
//剑指offer上的代码，同样对于范围没有限制的超时了；
if(index<=0) {
return 0;
}
int num = 0;
int count = 0;
while(count<index) {
++num;
if(isUgly(num)) {
count++;
}
}
return num;
}
//判断是否未丑数；
public boolean isUgly(int number) {
while(number%2==0) {
number /=2;
}
while(number%3==0) {
number /=3;
}
while(number%5==0) {
number /=5;
}
if(number==1) {
return true;
}else {
return false;
}
}
}
根据第二种思路写的代码
//执行通过，但是时间依然很高，50ms;对于任意的N依然不是一个好的解法
public static int GetUglyNumber_Solution(int index) {
if (index <= 0) {
return 0;
}
int[] arr = new int[index];
arr[0] = 1;
int num = 0; // 最大的位置；
while (num < index - 1) {
int M2 = 0;
int M3 = 0;
int M5 = 0;
int T2 = 0;
int T3 = 0;
int T5 = 0;
boolean flag2=false;
boolean flag3=false;
boolean flag5= false;
// 产生下一个丑数；
for (int i = 0; i <= num; i++) {
if(arr[i]*2>arr[num]&&!flag2) {
T2=i;
M2=arr[i]*2;
flag2 = true;
}
if(arr[i]*3>arr[num]&&!flag3) {
T3=i;
M3=arr[i]*3;
flag3 = true;
}
if(arr[i]*5>arr[num]&&!flag5) {
T5=i;
M5=arr[i]*5;
flag5 = true;
}
if(flag2&&flag3&&flag5) {
int temp = ((M2<M3)?M2:M3)<M5? ((M2<M3)?M2:M3):M5;
arr[++num]=temp;
break;
}
}
}
return arr[num];
}