剑指offer第二版-49.丑数

本系列导航：剑指offer（第二版）java实现导航帖

面试题49：丑数

题目要求：
我们把只包含因子2,3,5的数成为丑数。求按照从小到大的顺序第1500个丑数。1作为第一个丑数。

解题思路：
思路1：从1开始递增，依次判断每个数是否是丑数，不够高效；
思路2：思路1之所以效率低，比较关键的一点是遍历的每一个数字都进行丑数判断。思路2不是去判断丑数，而是计算出丑数：因为每个丑数都可以看成是由1去乘以2、3、5，再乘以2、3、5而衍生出来的。可以用三个指针指向第一个丑数1，三个指针分别表示乘2，乘3，乘5，将三个指针计算出来的最小的丑数放在数组中，并将该指针向后移动一个位置。为了得到第1500个丑数，需要一个长度1500的数组来记录已经计算出来的丑数。因此这个思路也可以说是用空间换时间。

package chapter5;

/**
 * Created with IntelliJ IDEA
 * Author: ryder
 * Date  : 2017/8/13
 * Time  : 9:47
 * Description:丑数
 **/
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开始的第num个丑数
    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，会有重复值，因此下面需要使用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));
    }
}

运行结果

12
12