4. 丑数 II

描述

设计一个算法，找出只含素因子2，3，5 的第 n 大的数。
符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

注意事项

我们可以认为1也是一个丑数

样例

如果n = 9， 返回 10

挑战

要求时间复杂度为O(nlogn)或者O(n)

思路

第一个最小数是1，将1乘以2,3,5往PriorityQueue里丢，从PriorityQueue中抛出最小值然后再乘以2,3,5，再加入PriorityQueue和已有元素进行比较，再抛出最小值乘以2,3,5往回丢，如此重复n 次操作；除此之外还需要一个hash表来去重，因为2 * 3 = 6， 而3 * 2也会出现6
注：
集合类型(List,Map,Set)要使用包装类型

代码

1. O(nlogn) HashMap + Heap
   在Java中PriorityQueue会自动把加入其中的数字从小到大排序

class Solution {
    /**
     * @param n an integer
     * @return the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        Queue<Long> Q = new PriorityQueue<Long>();
        HashSet<Long> inQ = new HashSet<Long>();
        Long[] primes = new Long[3];
        primes[0] = Long.valueOf(2);
        primes[1] = Long.valueOf(3);
        primes[2] = Long.valueOf(5);
        for (int i = 0; i < 3; i++) {
            Q.add(primes[i]);
            inQ.add(primes[i]);
         }
        // 第一个数
        Long number = Long.valueOf(1);
        for (int i = 1; i < n; i++) {
            // 从第二个数开始抛出 n-1 次
            number = Q.poll();
            for (int j = 0; j < 3; j++) {
                if (!inQ.contains(primes[j] * number)) {
                    Q.add(number * primes[j]);
                    inQ.add(number * primes[j]);
                }
            }
        }
        return number.intValue();
    }
}

相关知识点

intValue()的用法

1. intValue()是java.lang.Number类的方法，Number是一个抽象类。Java中所有的数值类都继承它。也就是说，不单是Integer有intValue方法，Double，Long等都有此方法。
2. 此方法的意思是：输出int数据。每个数值类中具体的实现是不同的。例如：
   Float类和Double类的intValue方法，就是丢掉了小数位，而Long的intValue方法又不一样的