4.Ugly Number II
1.Description(Medium)
Ugly number is a number that only have factors2
,3
and5
.
Design an algorithm to find the_n_th ugly number. The first 10 ugly numbers are1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
Notice
Note that1
is typically treated as an ugly number.
Example
Ifn=9
, return10
.
O(nlogn) or O(n) time.
LintCode Copyright Priority Queue
2.Code
这就是多链表Merge Sort的一个扩展题。对于任意一个ugly number - K, 2*K, 3*K, 和5*K都是ugly number,所以说新的ugly number都是从已有的ugly number上,通过与{2,3,5}相乘而产生的。
都是ugly number。只要不断把新产生的ugly number通过merge sort添加到原有的ugly number数组中就可以了,直到找到第N个。
public int nthUglyNumber(int n) {
ArrayList<Integer> list=new ArrayList<Integer>();
list.add(1);
int i2=0;
int i3=0;
int i5=0;
while(list.size()<n){
int m2=list.get(i2)*2;
int m3=list.get(i3)*3;
int m5=list.get(i5)*5;
int min=Math.min(m2, Math.min(m3, m5));
list.add(min);
if(min==m2) i2++;
if(min==m3) i3++;
if(min==m5) i5++;
}
return list.get(list.size()-1);
}
Last updated
Was this helpful?