Ugly Number II 4

Question

Ugly number is a number that only have factors 2, 3 and 5.

Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

Notice

Note that 1 is typically treated as an ugly number.

Example

If n=9, return 10.

Challenge

O(n log n) or O(n) time.

Solution

方法一：HashMap + PriorityQueue(MinHeap)：将2，3，5入队，每次取出堆顶元素（最小值），依次和3个factor相乘，将所得结果入队。用HashMap记录入队元素，入过队的元素不能再次入队。

方法二：以1为第一个元素，寻找比当前元素大的元素里面的最小者入队。每个factor用一个count来记录队列中第几个元素乘以factor以后恰好比current大，取3个factor结果里面的最小者作为下一个元素入队。

代码如下：

HashMap + Heap O(nlogn)：

class Solution {
    /**
     * @param n an integer
     * @return the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        // Write your code here
        //HashMap + Heap O(nlogn)

        if(n <= 0){
            return 0;
        }

        PriorityQueue<Long> Q = new PriorityQueue<Long>();
        HashMap<Long, Boolean> inQ = new HashMap<Long, Boolean>();
        Long[] prime = new Long[3];
        prime[0] = Long.valueOf(2);
        prime[1] = Long.valueOf(3);
        prime[2] = Long.valueOf(5);
        for(int i = 0; i < 3; i++){
            Q.add(prime[i]);
            inQ.put(prime[i], true);
        }

        //每次取最小堆（优先队列）顶的元素，取n-1次，同时将取出的数和3个factor相乘的结果加入队列（如果本来已经在队列中则不用加）
        Long number = Long.valueOf(1);
        for(int i = 1; i < n; i++){
            number = Q.poll();
            for(int j = 0; j < 3; j++){
                if(!inQ.containsKey(number * prime[j])){
                    Q.add(number * prime[j]);
                    inQ.put(number * prime[j], true);
                }
            }
        }
        //Long转换为Int
        return number.intValue();
    }
}

O(n):

class Solution {
    /**
     * @param n an integer
     * @return the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        // Write your code here
        //O(n)
        ArrayList<Integer> ugly = new ArrayList<Integer>();
        ugly.add(1);
        int p1 = 0, p2 = 0, p3 = 0;
        int min1 = 0, min2 = 0, min3 = 0;
        int current = 1;

        //用current记录当前元素，寻找比当前元素大的数里面的最小值作为下一个元素
        while(ugly.size() < n){
            while(ugly.get(p1) * 2 < current){
                p1++;
            }
            min1 = ugly.get(p1) * 2;

            while(ugly.get(p2) * 3 < current){
                p2++;
            }
            min2 = ugly.get(p2) * 3;

            while(ugly.get(p3) * 5 < current){
                p3++;
            }
            min3 = ugly.get(p3) * 5;

            int next = Math.min(min1, min2);
            next = Math.min(next, min3);

            current = next + 1;
            ugly.add(next);
        }

        return ugly.get(n - 1);
    }
}