丑数II

题意

设计一个算法，找出只含素因子2，3，5 的第 n 大的数。

符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

注意事项：我们可以认为 1 也是一个丑数

样例

如果n = 9， 返回 10

思路

其实改题的题意就是在所有 丑数 列表中，找到第 n 个丑数。

最简单的做法是从 1 开始，判断每一个数是否是一个丑数，是的话则加到丑数列表中，直到丑数列表的大小等于 n，但是这种方法效率较低，我们可以根据规律而尝试只创造出有效的丑数。

1*2=2 2*2=4  3*2=6  4*2=8  5*2=10 ...
1*3=3 2*3=6  3*3=9  4*3=12 5*3=15 ...
1*5=5 2*5=10 3*5=15 4*5=20 5*5=25 ...

观察规律可得，丑数是取已有的丑数乘以 2 或 3 或 5 得到的，那么我们可以先将特殊的丑数 1 放进丑数列表中。

因为已存在的丑数肯定在列表中是按照顺序存放的，所以对于乘以 2 而言，肯定存在一个丑数 p2，在它之前的每一个丑数乘以 2 都是当前列表中最后一个丑数的，通用，在它之后的每一个丑数乘以 2 的结果都是大于当前列表中最后一个丑数的，我们只需要记住 p2 的这个位置，同样存在的还有 p3 和 p5，记住这 3 个数的位置，就可以一些避免不必要的比较。

我们只需要取出 p2, p3, p5 位置的那个数，分别乘以 2, 3, 5 将结果最小的存入到丑数列表中即可。直到丑数列表的个数达到 n。

代码实现

public class Solution {
    /*
     * @param n: An integer
     * @return: the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        if (n == 1) {
            return 1;
        }
        List<Integer> uglys = new ArrayList<Integer>();
        uglys.add(1);
        
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n; i++) {
            int lastUgly = uglys.get(i - 1);
            while (uglys.get(p2) * 2 <= lastUgly) p2++;
            while (uglys.get(p3) * 3 <= lastUgly) p3++;
            while (uglys.get(p5) * 5 <= lastUgly) p5++;
            
            uglys.add(Math.min(
                Math.min(uglys.get(p2) * 2, uglys.get(p3) * 3),
                uglys.get(p5) * 5)
                );
        }
        
        return uglys.get(n -1);
    }
};

原题地址

LintCode：丑数II