【解题报告】lintcode4求第n个丑数

题意

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

解答

既然只有素数因子2，3，5，那么我们可以得知，第n个丑数肯定是前面某一个丑数乘以2，3，5的结果 那么，我们可以以此生成一个丑数表 但是，第n个丑数是多少呢，可以得知，是比前一个数大的最小丑数 我们设置三个计数器，记录乘2，3，5比当前最大的丑数还要大的下标 每次添加就从这三个下标的数乘2，3，5的结果中选最小的一个 如此循环，得到第n个

代码

class Solution {
    /**
     * @param n an integer
     * @return the nth prime number as description.
     */
  List<Integer> uglyList = new ArrayList<Integer>(){{this.add(1);this.add(2);this.add(3);this.add(4);this.add(5);this.add(6);}};
    public int nthUglyNumber(int n) {
        // Write your code here
        int p2 = 0,p3 = 0,p5 = 0,max = uglyList.get(uglyList.size() - 1);
        if (n <= uglyList.size())
            return uglyList.get(n-1);
        while (uglyList.size() < n) {
            while (uglyList.get(p2) * 2 <= max)
                p2++;
            while (uglyList.get(p3) * 3 <= max)
                p3++;
            while (uglyList.get(p5) * 5 <= max)
                p5++;
            int next = min(uglyList.get(p2) * 2, uglyList.get(p3) * 3, uglyList.get(p5) * 5);
            max = next;
            uglyList.add(next);
        }
        return max;
    }
    private int min(int a,int b,int c){
        int x = Math.min(a,b);
        int y = Math.min(x,c);
        return y;
    }
};