剣指offerプログラミング試験問題Java実現--33.ブス数
3397 ワード
個人ブログ:小景お兄ちゃん
33.ブス数
テーマ記述では,素因数2,3,5のみを含む数を醜数(Ugly Number)と呼ぶ.例えば、6、8はすべて醜数であるが、14は質量因子7を含むためではない.習慣的に私たちは1を最初の醜数と見なしています.小さいから大きい順のN番目の丑数を求めます.考え方:私たちは3つの数を比較するだけです:2に乗る最小の数、3に乗る最小の数、5に乗る最小の数
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);
}
}