牛客网|丑数
864 ワード
因子2,3,5のみを含む数をブス数(Ugly Number)と呼ぶ.例えば、6、8はすべて丑数であるが、14は因子7を含むためではない.習慣的に私たちは1を最初の醜数と見なしています.小さいから大きい順のN番目の丑数を求めます.
a,b,cはそれぞれ*2,*3,*5の位置を記録し,次の数はこの3つの数がそれぞれ*2,*3,*5で得られた数の最小のその数であり,配列に格納される.
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);
}