-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathUglyNumber.java
More file actions
77 lines (71 loc) · 2.2 KB
/
Copy pathUglyNumber.java
File metadata and controls
77 lines (71 loc) · 2.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package AlgorithmTest;
/*
*
* 题目:我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求从小到大的顺序的第 1500个丑数。
* */
public class UglyNumber {
public static void main(String[] args) {
System.out.println(findIndexOfUglyNumber(150));
System.out.println(BetterMethodOfUglyNumber(150));
}
public static int findIndexOfUglyNumber(int index){
int modIndex=0;
int num=1;
while(modIndex<index){
if (isUgly(num)){
modIndex++;
}
num++;
}
return --num;
}
public static boolean isUgly(int num){
while(num%2==0){
num /=2;
}
while(num%3==0){
num /=3;
}
while(num%5==0){
num /=5;
}
return num==1?true:false;
}
/*
*优化的核心是只操作丑数，而不操作其他数，时间复杂度大幅提高。
* */
public static int BetterMethodOfUglyNumber(int index){
int [] aimNumArray=new int[index]; //初始化目标数组
aimNumArray[0]=1; //1是第一个丑数
int nextIndex=1;// 从第二个丑数开始计算
/*
*
* */
int tIndexOf2=0;
int tIndexOf3=0;
int tIndexOf5=0;
while(nextIndex<index){
int minNum= min(aimNumArray[tIndexOf2]*2,aimNumArray[tIndexOf3]*3,aimNumArray[tIndexOf5]*5);
aimNumArray[nextIndex]=minNum;
/*
*z之前的丑数是有序排列的，所以为了优化算法，寻找边界值
* */
while(aimNumArray[tIndexOf2]*2<=aimNumArray[nextIndex]){
++tIndexOf2;
}
while(aimNumArray[tIndexOf3]*3<=aimNumArray[nextIndex]){
++tIndexOf3;
}
while(aimNumArray[tIndexOf5]*5<=aimNumArray[nextIndex]){
++tIndexOf5;
}
++nextIndex;
}
return aimNumArray[nextIndex-1];
}
//求出三个值的最小值
public static int min(int numfor2,int numfor3,int numfor5){
int min=numfor2>numfor3 ? numfor3:numfor2;
return min=min>numfor5?numfor5:min;
}
}