编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:  

1. 1 是丑数。

2. n 不超过1690。

答案：

 1public int nthUglyNumber(int n) {
 2    if (n <= 1)
 3        return n;
 4    int t2 = 0, t3 = 0, t5 = 0;
 5    int[] k = new int[n];
 6    k[0] = 1;
 7    for (int i = 1; i < n; i++) {
 8        k[i] = Math.min(k[t2] * 2, Math.min(k[t3] * 3, k[t5] * 5));
 9        if (k[i] == k[t2] * 2)
10            t2++;
11        if (k[i] == k[t3] * 3)
12            t3++;
13        if (k[i] == k[t5] * 5)
14            t5++;
15    }
16    return k[n - 1];
17}

解析：

丑数除了第一个是0以外，其他的都可以这样表示

1*（2，3，5），

2*（2，3，5），

3*（2，3，5），

4*（2，3，5），

……………………

题目中说要找到第n个丑数，这n个丑数都是按照从小到大的顺序查找的。所以每次查找的时候都是找最小的。下面再来看一种解法

 1public int nthUglyNumber(int n) {
 2    if (n == 1)
 3        return 1;
 4    PriorityQueue<Long> q = new PriorityQueue();
 5    q.add(1L);
 6    for (long i = 1; i < n; i++) {
 7        long tmp = q.poll();
 8        while (!q.isEmpty() && q.peek() == tmp)
 9            tmp = q.poll();
10        q.add(tmp * 2);
11        q.add(tmp * 3);
12        q.add(tmp * 5);
13    }
14    return q.poll().intValue();
15}

PriorityQueue默认是一个小顶堆的优先队列，poll表示的是移除最顶端的元素，也是最小的元素，然后再用最小的元素分别和2,3,5进行相乘，add方法加入到队列的时候又会进行排序，保证最顶端的元素是最小的。