题目描述
设计一个算法，找出只含素因子2，3，5 的第 n 大的数。1也是一个丑数。
思路
方法一
每个丑数都是2*..3..5..的结果
创建保存丑数的数组a，设a[0]=1
用index2，index3，index5表示丑数分解包含了2、3、5的个数，初始化为0
每次求min(a[indexk]*k)，得到当前最小的丑数，写入数组，并将indexk++
这样做即可保证a数组中能保存所有的按序排列的丑数，输出第a[n-1]个元素即可。
方法二
将1加入保存丑数的数组a，将2,3,5加入优先队列pq
每次从pq取min，如果min与a[tmp]不等，数组保存min，并将min*2,3,5的值加入优先队列。如果相等，跳过。
这样做，最终可以得到a[n-1]个元素即为结果
代码
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
| int nthUglyNumber(int n) {
// Write your code here
int index2 = 0;
int index3 = 0;
int index5 = 0;
int[] res = new int[n];
res[0] = 1;
int count = 1;
while(count < n){
res[count] = min(res[index2]*2, res[index3]*3, res[index5]*5);
if(res[count] == res[index2]*2) index2++;
if(res[count] == res[index3]*3) index3++;
if(res[count] == res[index5]*5) index5++;
count++;
}
return res[--count];
}
private int min(int a1, int a2, int a3){
if(a1 < a2){
if(a1 < a3)
return a1;
else
return a3;
}else if(a2 < a3){
return a2;
}else{
return a3;
}
}
|
考差点