LintCode：4 · 丑数 II

问题描述

如果一个数只有质数因子2，3，5 ，那么这个数是一个丑数。
前10个丑数分别为 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...设计一个算法，找出第N个丑数。
我们可以认为 1 也是一个丑数。

样例

输入： n = 1                  9
输出：     1                 10

解题思路

1. 首先，暴力的解题肯定是不行的，效率很低（暴力的解题思路：从1开始循环，每次判断下是不是丑数，然后+1继续，直到找到第n个丑数）；

2. 然后，我们回到丑数的定义，再次理解一下丑数：
   丑数可以表示成：2^x3^y5^z，则每个丑数通过 *2, *3, or *5 操作都将得到一个新的丑数；
   为了保证不漏掉任何一个丑数，就必须。
   注意：会有重复的丑数，需要进行去重。

3. 通过1的操作，我们确实可以得到丑数数组，但还有一个问题是该如何找到第n个丑数?
   

具体解题步骤

1. 建立一个丑数数组，初始只有一个1；

2. 建立一个循环：
   A. 从i=1开始，当i<n时结束，每次执行完i++（第1次执行，得到第2个丑数，第n-1次执行，得到第n个丑数）
   B. 循环中的逻辑：取数组第[i-1]位数，将它*2、*3、*5得到的数添加到数组里，并对数组进行去重、排序操作。

3.返回数组中第n-1位。

代码示例（JAVA）

TreeSet的本质是一个"有序的，并且没有重复元素"的集合，在这里利用TreeSet来完成去重、排序;
pollFirst()方法用于返回第一个最小元素，然后从此TreeSet中删除第一个元素。

public class Solution {
    public int nthUglyNumber(int n) {
        TreeSet<Long> nums = new TreeSet<>();

        long num = 1;
        for (int i = 1; i < n; i++) {
            nums.add(num * 2);
            nums.add(num * 3);
            nums.add(num * 5);
            num = nums.pollFirst();
        }
        
        return (int) num;
    }
}