剣指offerプログラミング試験問題Java実現--33.ブス数

3397 ワード

個人ブログ:小景お兄ちゃん
33.ブス数
テーマ記述では,素因数2,3,5のみを含む数を醜数(Ugly Number)と呼ぶ.例えば、6、8はすべて醜数であるが、14は質量因子7を含むためではない.習慣的に私たちは1を最初の醜数と見なしています.小さいから大きい順のN番目の丑数を求めます.考え方:私たちは3つの数を比較するだけです:2に乗る最小の数、3に乗る最小の数、5に乗る最小の数

import java.util.ArrayList;
public class Solution {

    public int GetUglyNumber_Solution(int n){
        if(n<=0)return 0;
        ArrayList<Integer> list=new ArrayList<Integer>();
        list.add(1);
        int i2=0,i3=0,i5=0;
        while(list.size()<n)//     
        {
            int m2=list.get(i2)*2;
            int m3=list.get(i3)*3;
            int m5=list.get(i5)*5;
            int min=Math.min(m2,Math.min(m3,m5));
            list.add(min);
            if(min==m2)i2++;
            if(min==m3)i3++;
            if(min==m5)i5++;
        }
        return list.get(list.size()-1);
    }
}