Ugly Number II

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.

Solution: PriorityQueue. O(nlogn). The long type is to avoid overflow.

public int nthUglyNumber(int n) {
    if(n <= 0) {
        return 0;
    }
    PriorityQueue<Long> pq = new PriorityQueue<Long>();
    HashSet<Long> set = new HashSet<Long>();
    pq.offer(1l);
    int[] numbers = new int[]{2, 3, 5};
    long res = 0;
    for(int i = 0; i < n; i++) {
        long tmp = pq.poll();
        res = tmp;
        for(int j = 0; j < 3; j++) {
            if(!set.contains(tmp * numbers[j])) {
                pq.offer(tmp * numbers[j]);
                set.add(tmp * numbers[j]);
            }
        }
    }
    return (int)res;
}

Solution: Everytime select minimum value from 2, 3, 5 times.

public int nthUglyNumber(int n) {
    if(n <= 0) {
        return 0;
    }
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    int x = 0, y = 0, z = 0;
    while(list.size() < n) {
        int two = list.get(x) * 2;
        int three = list.get(y) * 3;
        int five = list.get(z) * 5;
        list.add(Math.min(two, Math.min(three, five)));
        if(list.get(list.size() - 1) == two) {
            x++;
        }
        if(list.get(list.size() - 1) == three) {
            y++;
        }
        if(list.get(list.size() - 1) == five) {
            z++;
        }
    }
    return list.get(list.size() - 1);
}