本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖
面試題49：丑數(shù)
題目要求：
我們把只包含因子2,3,5的數(shù)成為丑數(shù)。求按照從小到大的順序第1500個(gè)丑數(shù)黔州。1作為第一個(gè)丑數(shù)。
解題思路：
思路1：從1開(kāi)始遞增，依次判斷每個(gè)數(shù)是否是丑數(shù)，不夠高效咆蒿；
思路2：思路1之所以效率低，比較關(guān)鍵的一點(diǎn)是遍歷的每一個(gè)數(shù)字都進(jìn)行丑數(shù)判斷蚂子。思路2不是去判斷丑數(shù)沃测，而是計(jì)算出丑數(shù)：因?yàn)槊總€(gè)丑數(shù)都可以看成是由1去乘以2、3食茎、5蒂破，再乘以2、3董瞻、5而衍生出來(lái)的寞蚌√锇停可以用三個(gè)指針指向第一個(gè)丑數(shù)1钠糊，三個(gè)指針?lè)謩e表示乘2，乘3壹哺，乘5抄伍，將三個(gè)指針計(jì)算出來(lái)的最小的丑數(shù)放在數(shù)組中，并將該指針向后移動(dòng)一個(gè)位置管宵。為了得到第1500個(gè)丑數(shù)截珍，需要一個(gè)長(zhǎng)度1500的數(shù)組來(lái)記錄已經(jīng)計(jì)算出來(lái)的丑數(shù)。因此這個(gè)思路也可以說(shuō)是用空間換時(shí)間箩朴。
package chapter5;
/**
* Created with IntelliJ IDEA
* Author: ryder
* Date : 2017/8/13
* Time : 9:47
* Description:丑數(shù)
**/
public class P240_GetUglyNumber {
public static int getUglyNumber(int num){
if(num<=0)
return 0;
int number = 0,uglyFound = 0;
while (uglyFound<num){
number++;
if(isUgly(number))
uglyFound++;
}
return number;
}
public static boolean isUgly(int number){
while (number%2==0)
number/=2;
while (number%3==0)
number/=3;
while (number%5==0)
number/=5;
return number==1;
}
//獲取從1開(kāi)始的第num個(gè)丑數(shù)
public static int getUglyNumber2(int num){
int[] uglyNumber = new int[num];
uglyNumber[0] = 1;
int uglyIndex=0, multiply2=0, multiply3=0, multiply5=0;
while (uglyIndex+1<num){
uglyNumber[++uglyIndex] = min(uglyNumber[multiply2]*2,uglyNumber[multiply3]*3,uglyNumber[multiply5]*5);
//2*3=6岗喉，3*2=6，會(huì)有重復(fù)值炸庞，因此下面需要使用if钱床，而不能用if-else
if(uglyNumber[multiply2]*2==uglyNumber[uglyIndex])
multiply2++;
if(uglyNumber[multiply3]*3==uglyNumber[uglyIndex])
multiply3++;
if(uglyNumber[multiply5]*5==uglyNumber[uglyIndex])
multiply5++;
}
return uglyNumber[num-1];
}
public static int min(int x,int y,int z){
int temp = x<y?x:y;
return temp<z?temp:z;
}
public static void main(String[] args){
System.out.println(getUglyNumber(10));
System.out.println(getUglyNumber2(10));
}
}
運(yùn)行結(jié)果
12
12
