Ugly Number II

LC 264

每一个 Ugly Number 必须是 ugly number * 2, 3， 5

We can find that every subsequence is the ugly-sequence itself (1, 2, 3, 4, 5, 6，8…) multiply 2, 3, 5. Then we use similar merge method as merge sort, to get every ugly number from the three subsequence.

Time Complexity: O(n) Storage Complexity: O(n)

public class Solution {
    public int nthUglyNumber(int n) {
        if(n == 0 || n == 1) return n;
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(1);
        int res = 0;
        int l2 = 0;
        int l3 = 0;
        int l5 = 0;

        for(int i = 1; i < n; i++){
            while(list.get(l2) * 2 <= list.get(list.size() - 1)){
                l2++;
            }
             while(list.get(l3) * 3 <= list.get(list.size() - 1)){
                l3++;
            } 
             while(list.get(l5) * 5 <= list.get(list.size() - 1)){
                l5++;
            }              
            res = Math.min(Math.min(list.get(l2) * 2, list.get(l3) * 3), list.get(l5)* 5);
            list.add(res);
            if(res == list.get(l2) * 2){
                l2++;
            }
            if(res == list.get(l3) * 3){
                l3++;
            }
            if(res == list.get(l5) * 5){
                l5++;
            }
        }
        return res;

    }
}

PriorityQueue solution

class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> queue = new PriorityQueue<>();
        if (n == 1) return 1;
        queue.add(1l);
        long res = 1;
        for (int i = 1; i <= n; i++) {
            res = queue.poll();
            if (!queue.contains(res * 2)) queue.add(res * 2);
            if (!queue.contains(res * 3)) queue.add(res * 3); 
            if (!queue.contains(res * 5)) queue.add(res * 5);
        }
        return (int)res;
    }
}