4.Ugly Number II

1.Description(Medium)

Ugly number is a number that only have factors2,3and5.

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 that1is typically treated as an ugly number.

Example

Ifn=9, return10.

Challenge

O(nlogn) or O(n) time.

Tags

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);       
    }