牛客网|丑数

864 ワード

因子2,3,5のみを含む数をブス数(Ugly Number)と呼ぶ.例えば、6、8はすべて丑数であるが、14は因子7を含むためではない.習慣的に私たちは1を最初の醜数と見なしています.小さいから大きい順のN番目の丑数を求めます.
a,b,cはそれぞれ*2,*3,*5の位置を記録し,次の数はこの3つの数がそれぞれ*2,*3,*5で得られた数の最小のその数であり,配列に格納される.
public static int GetUglyNumber_Solution(int index) {
        if (index<=0)   return 0;
        int a=0,b=0,c=0;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        while(list.size()<index)
        {
            int next = Math.min(Math.min(list.get(a)*2,list.get(b)*3),list.get(c)*5);
            if(next == list.get(a)*2)   a++;
            if(next == list.get(b)*3)   b++;
            if(next == list.get(c)*5)   c++;
            list.add(next);
        }


        return list.get(index-1);
    }