丑数

题目描述：
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

package Demo01;


import java.util.ArrayList;

import static java.lang.Math.min;

public class UglyArray {

    public static void main(String[] args) {
        System.out.println(uglyArray(10));
    }
    public static int uglyArray(int index){

        /*
        通过计算，丑数数组  [1,2,3,4,5,6,8,9,10,12，.....]
        1为第一个丑数，加入集合
        此时uglyarr 为[1],t2 == 0, t3==0, t5==0;
        （1）
        *2 :2
        *3: 3
        *5 : 5
        把最小的 2 作为第二个丑数加入集合List,此时 t2 == 1, t3 == 0, t5 == 0
        (2)
        uglyarr 为[1,2],t2 == 1, t3==0, t5==0;
         *2 :4
        *3: 3
        *5 : 5

        把最小的3 加入丑数集合list，此时uglyarr为[1,2,3],t2==1,t3==1,t5==0

        (3)uglyarr为[1,2,3],t2==1,t3==1,t5==0

        *2 :4
        *3: 6
        *5 : 5
        把最小的丑数 4 加入集合list， 此时uglyarr为[1,2,3，4],t2==2,t3==1,t5==0

        以此类推

         */

        if(index < 7){
            return index;
        }

        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);

        int t2 = 0, t3 = 0, t5 = 0;
        for(int i = 1; i < index; i++){
            //下一个丑数，一定是他们中的最小值
            int ugly = min(list.get(t2) * 2,min(list.get(t3) * 3, list.get(t5) * 5));
            list.add(ugly);

            //看是哪个中来的丑数，*2，*3，*5
            if(list.get(t2) * 2 == list.get(i)){
                t2++;
            }

            if(list.get(t3) * 3 == list.get(i)){
                t3++;
            }

            if(list.get(t5) * 5 == list.get(i)){
                t5++;
            }
        }

        //返回第N个丑数
        return list.get(index - 1);
    }
}

本文地址：https://blog.csdn.net/qq_43515131/article/details/107271151