264. 丑数 II

编写一个程序，找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例:

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

1 是丑数。
n 不超过1690。

image.png

分析：除了第一个丑数1以外 每一个丑数都是 由 2，3，5，
 乘以原有的丑数集合{1。。。。}，来扩充，
注意一点，在该题目中每次扩充一位即可，
每次都要比较，（2，3，5）所乘得到的数，
选择最小的数
（，加入丑数集合中，此时，将刚刚被乘以的那个（
2，3，5）去乘以，集合中的下一个数
（可能会相等，此时那相等的数，同时乘以集合的下一个）。



（2，3，5）每个都数都要乘以丑数数组中的每一个数，
设每个（2，3，5）都有一个指针（都在遍历丑数数组），
当乘以丑数数组的积为最小时
（若相等，指针都会指向下一个），
指针指向下一个，依次类推。

*/
class Solution {
    public int nthUglyNumber(int n) {
        
        
        int [] res = new int[n];
       res[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0,k = 0;
        for( k = 1;k<n;k++) {
            int m2 = res[i2] * 2, m3 = res[i3] * 3, m5 = res[i5] * 5;
            int mn = Math.min(m2, Math.min(m3, m5));
            if (mn == m2) ++i2;
            if (mn == m3) ++i3;
            if (mn == m5) ++i5;
            res[k] = mn;
        }
        return res[k-1];
        
        
    }
}

leetcode 原题