丑数问题，力扣264，坑点

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

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。
正确源码：

class Solution {
    public  static int nthUglyNumber(int n) {
        int p2=1;
        int p3=1;
        int p5=1;
        int[] ugly=new int[n+1];
        ugly[1]=1;
        for(int i=2;i<=n;i++){
            ugly[i]=Math.min(Math.min(3*ugly[p3],5*ugly[p5]),2*ugly[p2]);
            if(ugly[i]==2*ugly[p2]){
                p2++;
            }
            if(ugly[i]==3*ugly[p3]){
                p3++;
            }
            if(ugly[i]==5*ugly[p5]){
                p5++;
            }
        }
        return ugly[n];
    }
}

解读：
可以看出任何一个丑数都必定是前面的某一个比他小的丑数，乘以2或者3或者5得到的
因此只需要把所求丑数之前的所有丑数乘以2，3，5，然后找最小的即可
例如：最开始是求第二个丑数

2最小

然后是第三个丑数

3最小，第三个丑数是3
接着是第四个丑数

4最小，第四个丑数是4
这样做下去肯定是可以找到第n个丑数的，可是，是不是太复杂了，时间复杂度非常大
因此进行优化
首先，很明显丑数是递增的
因此在下面的图中

下一个丑数是5，他是5乘以某一个丑数得到的，10和15和20都是5乘以某一个丑数

但是在5没有被排好之前。是不可能轮到他们的，因为丑数是递增的数列，因此把他们乘出来，就是无用功，所以就可以拿一个指针p5来记录5乘到哪一个丑数了

对于其他因子2和3也是同理，一旦乘了某个丑数，对应的指针就加加

ugly[i]=Math.min(Math.min(3*ugly[p3],5*ugly[p5]),2*ugly[p2]);
            if(ugly[i]==2*ugly[p2]){
                p2++;
            }else if(ugly[i]==3*ugly[p3]){
                p3++;
            }else if(ugly[i]==5*ugly[p5]){
                p5++;
            }

坑点：下面的代码是错的

class Solution {
    public  static int nthUglyNumber(int n) {
        int p2=1;
        int p3=1;
        int p5=1;
        int[] ugly=new int[n+1];
        ugly[1]=1;
        for(int i=2;i<=n;i++){
            ugly[i]=Math.min(Math.min(3*ugly[p3],5*ugly[p5]),2*ugly[p2]);
            if(ugly[i]==2*ugly[p2]){
                p2++;
            }else if(ugly[i]==3*ugly[p3]){
                p3++;
            }else if(ugly[i]==5*ugly[p5]){
                p5++;
            }
        }
        return ugly[n];
    }
}

区别就在于，正确代码用的三个if，错误代码用的是else if。
错误代码过不了，放idea编译器里面发现会产生一些相同的重复丑数。
因为有可能2$\times$ugly[p2]与3$\times$ugly[p3]与5$\times$ugly[p5]这三个中有至少两个相等,
假设是2$\times$ugly[p2]和5$\times$ugly[p5]相等，这个时候p2和p5都要同时加加
而用else if就只会加一次，所以会有重复的丑数