设计一个算法，找出只含素因子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)要使用包装类型
代码
- 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()的用法
- intValue()是java.lang.Number类的方法，Number是一个抽象类。Java中所有的数值类都继承它。也就是说，不单是Integer有intValue方法，Double，Long等都有此方法。
- 此方法的意思是：输出int数据。每个数值类中具体的实现是不同的。例如：
Float类和Double类的intValue方法，就是丢掉了小数位，而Long的intValue方法又不一样的
