forked from algorithm010/algorithm010
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLC_264_ugly_number_ii.java
More file actions
40 lines (34 loc) · 1.53 KB
/
LC_264_ugly_number_ii.java
File metadata and controls
40 lines (34 loc) · 1.53 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
package Week02;
import java.util.HashMap;
public class LC_264_ugly_number_ii {
/*
* 一开始，丑数只有{1}，1可以同2，3，5相乘，取最小的1×2=2添加到丑数序列中。
现在丑数中有{1，2}，在上一步中，1已经同2相乘过了，所以今后没必要再比较1×2了，我们说1失去了同2相乘的资格。
现在1有与3，5相乘的资格，2有与2，3，5相乘的资格，但是2×3和2×5是没必要比较的，因为有比它更小的1可以同3，5相乘，所以我们只需要比较1×3，1×5，2×2。
依此类推，每次我们都分别比较有资格同2，3，5相乘的最小丑数，选择最小的那个作为下一个丑数，假设选择到的这个丑数是同i（i=2，3，5）相乘得到的，所以它失去了同i相乘的资格，把对应的pi++，让pi指向下一个丑数即可。
* */
public int nthUglyNumber(int n) {
if (n<=0) {
return 0;
}
int[] ugly = new int[n];
ugly[0]=1;
int index1=0,index2=0,index3=0,i =1;
while(i<n){
//找到最小的丑数，存在ugly[i]
ugly[i] = Math.min(ugly[index1]*2,Math.min(ugly[index2]*3,ugly[index3]*5));
//倒回去找相应的下标存起来
if(ugly[index1]*2==ugly[i]) {
index1++;
}
if(ugly[index2]*3==ugly[i]) {
index2++;
}
if(ugly[index3]*5==ugly[i]) {
index3++;
}
i++;
}
return ugly[n-1];
}
}