寻找丑数

编程练习

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

思路：这道题看似简单，实际要通过很难。首先想到的方法是先实现一个判断给定整数是否是丑数的方法，然后对从1到N的所有整数调用该方法，得到N以内的所有丑数，最后根据输入的参数index找出第index个即可。

java代码如下：

import java.util.ArrayList;

public class GetUglyNumber {
    public static int GetUglyNumber_Solution(int index) {
        if(index<0) {
        	return -1;
        }
        if(index==0) {
        	return 0;
        }
        ArrayList<Integer> list=new ArrayList<Integer>();
        //保证产生的丑数list足够大可以包括第index个丑数在内
        produceUglyNumber(list,index*index);
        
    	return list.get(index-1);
    }
    /**
     * 判断输入n是否是丑数
     * @param n
     * @return
     */
    public static boolean isUglyNumber(int n) {
    	if(n<0) {
    		return false;
    	}
    	ArrayList<Integer> list=new ArrayList<Integer>();
    	//求出n的所有因子
    	for(int i=1;i<=n;i++) {
    		if(n%i==0) {
    			list.add(i);
    		}
    	}
    	//判断是否只含有2,3,5因子(1和它本身除外)
    	//n如果是2,3或者5的整数倍，则n可以被除去
    	if(n%2==0 || n%3==0 || n%5==0) {
    		list.remove(list.indexOf(n));
    	}
    	while(list.contains(1)) {
    		list.remove(list.indexOf(1));
    	}
    	while(list.contains(2)) {
    		list.remove(list.indexOf(2));
    	}
    	while(list.contains(3)) {
    		list.remove(list.indexOf(3));
    	}
    	while(list.contains(5)) {
    		list.remove(list.indexOf(5));
    	}
    	/**
    	 * 排除因子中是2,3,5三个因子的整数倍的丑数，比如12的因子有1,2,3,4,6,12，上面的步骤只能排除1,2,3,12。
    	 * 对于4,6没法排除，所以需要递归判断4,6,是否是丑数，若是就除去。
    	 */
    	for(int i=0;i<list.size();){
    		if(list.get(0)%2==0 || list.get(0)%3==0 || list.get(0)%5==0) {
    			if(isUglyNumber(list.get(0))) {
    				list.remove(0);
    			}
    		}else {
    			break;
    		}
    	}
    	//移出2,3,5和1，以及符合条件的n本身以外，如果还有因子，则说明不是丑数，反之则是丑数
    	if(list.size()==0) {
    		return true;
    	}
    	return false;
    }
    /**
     * 产生给定整数n以内(包括n)的所有丑数
     * @param uglyNumberList 存放丑数的arraylist
     * @param n
     */
    public static void produceUglyNumber(ArrayList<Integer> uglyNumberList,int n){
    	for(int i=1;i<=n;i++) {
    		if(isUglyNumber(i)) {
    			uglyNumberList.add(i);
    		}
    	}
    }
    public static void main(String[] args) {
		int n=1000;
		GetUglyNumber_Solution(n);
		
	}
}

　　但是实际实现中发现，丑数的增长速度远远大于其个数的增长，如果你想要得到第1500个丑数，你要获取到的丑数list中的最大值N至少得为859963392，而对这么大的数做for循环统计N以内的丑数，很耗费时间，我一开始就是用的这个方法，提交时提示超时，本地跑了十几秒才跑出来第1500个丑数859963392。毕竟是自己想出来的方法，不忍心就这么抛弃，所以想着改进算法，后来看到别人写的一个判断丑数的方法比我的要效率高，所以拿过来用了一下，该方法是我见过最简单易懂且效率高的判断丑数的方法，下面贴出来记录一下。

/**
    * 判断一个数是不是丑数
    * @param n
    * @return
    */
   public static boolean isUglyNumber(int n) {
   	while(n%2==0) {
   		n/=2;
   	}
   	
   	while(n%3==0) {
   		n/=3;
   	}
   	while(n%5==0) {
   		n/=5;
   	}
   	return (n==1);
   }

　　通过改进丑数判断以及查找算法，可以将输入1500的结果优化到十秒左右完成，还是太慢，效率太低。遂放弃该方法，开始考虑丑数生成的规律，从规律入手来尝试新的算法。先写出10以内的丑数，即1,2,3,4,5,6,8,9,10；可见除了1以外，每个数字都可以写成前几个数字x2,x3,x5的形式。比如2=1x2,3=1x3,4=2x2,5=1x5,6=2x3,8=4x2,9=3x3,10=2x5。可以估计后面的所有丑数都可以由前边的丑数乘以丑数因子2,3,5得到，所以考虑如下算法：

1. 首先确定第一个丑数为1，然后计算1x2,1x3,1x5的值，取出其中大于1的最小的数作为下一个丑数，此时得到的是2；
2. 完成第一步后，此时的丑数序列为1,2。分别计算1x2=2,1x3=3,1x5=5,2x2=4,2x3=6,2x5=10。再挑出其中大于2的值为3,5,4,6,10，取最小值3作为下一个丑数。
3. 以此类推……
4. 要计算第i个丑数，分别计算前i-1个丑数乘以2,3,5因子中的大于第i-1个丑数的最小值即可。

java代码如下：

import java.util.ArrayList;

public class GetUglyNumber3 {
    public static int GetUglyNumber_Solution(int index) {
        if(index<0) {
        	return -1;
        }
        if(index==0) {
        	return 0;
        } 
        if(index==1) {
        	return 1;
        }
        //定义存放挨个生成的丑数的数组,并添加第一个丑数1,至于为什么是1691，可以去我的博客找到答案https://irisqp.github.io
        int [] arr= new int[1691];
        arr[0]=1;
        int count=1;
        //循环生成第index个丑数
        while(true) {
        	int m2=0;
        	int m3=0;
        	int m5=0;
        	/**
        	 * 将最新的丑数之前的所有丑数*2,求出其中大于最新的丑数的最小值，将其赋给m2;
        	 */
        	for(int i=0;i<count;i++) {
        		if(arr[i]*2>arr[count-1]) {
        			m2=arr[i]*2;
        			break;
        		}	
        	}
        	/**
        	 * 将最新的丑数之前的所有丑数*3,求出其中大于最新的丑数的最小值，将其赋给m3;
        	 */
        	for(int i=0;i<count;i++) {
        		if(arr[i]*3>arr[count-1]) {
        			m3=arr[i]*3;
        			break;
        		}	
        	}
        	/**
        	 * 将最新的丑数之前的所有丑数*5,求出其中大于最新的丑数的最小值，将其赋给m5;
        	 */
        	for(int i=0;i<count;i++) {
        		if(arr[i]*5>arr[count-1]) {
        			m5=arr[i]*5;
        			break;
        		}	
        	}
        	//求出m2,m3,m5中的最小值，作为下一个最新的丑数
        	int min=compare(m2,m3,m5);
        	arr[count]=min;
        	count++;
        	//如果生成的丑数个数达到给定的要求，则返回最新生成的这个丑数
        	if(count==index) {
        		return arr[count-1];
        	}
        	
        }    
    }
    
    /**
     * 三个整数比较大小，返回最小的那个
     * @param a
     * @param b
     * @param c
     * @return
     */
    public static int compare(int a,int b,int c) {
    	
    	if(a<=b) {
    		if(c<=a) {
    			return c;
    		}else {
    			return a;
    		}
    	}else if(c>=b){
    		return b;
    	}else {
    		return c;
    	}
    }
    
    public static void main(String[] args) {
		int n=1500;
		System.out.println(GetUglyNumber_Solution(n));
	}
}

　　此代码可以很快的计算出n比较大时的第n个丑数，在牛客网上通过的时间为48ms，因为它生成的每一个数都是丑数，省去了很多不必要的循环次数，至于为什么我定义的存放丑数的int数组大小为1691，是因为我经过测试后发现第1691个丑数的值为2125764000，而java中int型的可以表示的整数的最大值为2147483648 ，经过测试第1692个丑数就会超出这个范围，因为题目要求返回类型为int型，所以设置1691大小的数组完全够用了，避免了存储空间的浪费。