剑指offer-例题丑数

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 

解法一：

public class Solution { public int GetUglyNumber_Solution(int index) { if(index<=0) return 0; int sum=0; int i; for(i=1;sum<index;i++) { if(isUgly(i)==true)//if(isUgly2(i)==true) sum++; } i--;//这里是个坑 return i; } //循环法 public boolean isUgly(int num) { if(num<=0) return false; while(num%2==0) num/=2; while(num%3==0) num/=3; while(num%5==0) num/=5; if(num==1) return true; else return false; } //递归法 public boolean isUgly2(int num) { if(num<=0) return false; if(num==1) return true; if(num%2==0) return isUgly2(num/2); if(num%3==0) return isUgly2(num/3); if(num%5==0) return isUgly2(num/5); return false; } }

缺点：对每一个整数都需要做整除、取余操作以判断其是否为丑数，将大量的时间浪费在对非丑数的操作上

解法二：

1、只计算丑数，以节省时间：丑数是另一个丑数乘以2、3、5的结果

2、利用数组存放已找到的丑数：以空间换时间

      这样才能找到后面的丑数

3、要找的丑数是从大到小排序中的第index个，因此数组中存储的丑数必须是从小到大排好序的

4、每次只需要找到下 一 个丑数，并保证数组内存储的丑数都是按大小顺序排列的

     下一个丑数只能是数组内各丑数 *2、*3、*5中最小的一个，同时又要比当前数组内最大的丑数还要大，因为比它小的已经存在于数组中，无意义

     数组内总存在一个下标in2，使得其前面的丑数*2<当前数组内最大丑数（其实这些已经存在与数组中，不需要再填入），其及其后的丑数*2>当前数组内最大丑数

     数组内总存在一个下标in3，使得其前面的丑数*3<当前数组内最大丑数（其实这些已经存在与数组中，不需要再填入），其及其后的丑数*3>当前数组内最大丑数

    数组内总存在一个下标in5，使得其前面的丑数*5<当前数组内最大丑数（其实这些已经存在与数组中，不需要再填入），其及其后的丑数*5>当前数组内最大丑数

    所以每次只需找到 result[in2]*2、result[in3]*3、result[in5]*5 三者中最小的一个加入数组中

public class Solution { public int GetUglyNumber_Solution(int index) { if(index<=0) return 0; int[] result=new int[index]; result[0]=1; int in2=0; int in3=0; int in5=0; for(int i=1;i<index;i++) { result[i]=Math.min(2*result[in2],Math.min(3*result[in3],5*result[in5])); if(result[i]==2*result[in2]) in2++; if(result[i]==3*result[in3]) in3++; if(result[i]==5*result[in5]) in5++; } return result[index-1]; } }