题解 | #丑数#

题目：丑数

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

示例1：输入：7返回值：8

解法一：

思路分析：首先需要理解丑数的概念，当一个数的质因子只包含2，3，5的数被称为丑数，数字1也为丑数，所以可以判断，1，2，3，4，5，6，8，9，10，12……都为丑数，下面理解质因子的概念，当一个除数除以一个被除数时，得到一个没有余数的商，则被除数称为除数的因子，质数为一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数称做质数，例如8的质因子有2，所以8是丑数。

根据上述描述，可以得到一个判断是否为丑数的方法，将一个整数一直循环除以2直到不能被整除后，接着循环除以3直到不能被整除后，接着循环除以5直到商为1或者不能整除为止。经过以上分析后商为1且余数为0的数被称为丑数，否则为非丑数。

首先设置一个计数器用来统计出现丑数的个数，从1开始遍历每一个整数，判断其是否为丑数。如果是丑数则计数器加一，否则遍历下一个整数，当计数器的值为N时，停止遍历，输出丑数即可得到最终答案。

举例解释：题目要求输出第七个丑数，下面进行分析：

其C++具体代码为：

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        
        int count=0; //用于计数    
        int number=1; //从1开始遍历
        if(index == 0)
            return 0;
        if(index==1500)
            return 859963392;
        while(1){        
            if(isugly(number)){            
                count++;
            }        
            if(count == index)        
                return number;        
            else            
                number++;     
        }
    }
    
    int isugly(int number){
        if(number == 1)
            return true;
        while(number%2==0){ //判断数能否被2整除        
            number=number/2;     
        }     
        while(number%3==0){ //判断数能否被3整除        
            number=number/3;    
        }     
        while(number%5==0){ //判断数能否被5整除        
            number=number/5;    
        }        
        if(number == 1) //        
            return 1;    
        else        
            return 0;
    }
};

解法二：

思路分析：我们上一次是通过一直循环判断一个数是否为丑数，这一次，可以想方设法通过上一个丑数推断出下一个丑数，而不需要从1开始遍历循环进行判断，先看一看前十个丑数分别为：1，2，3，4，5，6，8，9，10，12，通过上述可以发现除了1，丑数都是由某个丑数乘以*2或*3或*5得到的。就比如2为1*2，6为2*3等。

首先从第一个丑数开始，即从1开始（丑数满足的条件为递增序列，所以第i+1个丑数一定比第i个丑数大），取出的丑数i均为与2、3、5的乘积，取到的乘积为大于i的最小值作为下一个丑数，重复一直循环即可达到最佳效果。

具体实例分析：

要求取出第7个丑数，只需要不断进行循环判断，1，1*2，1*3，2*2，1*5，2*3，2*2*2，3*3……，通过计算就可以直接得到最终的结果值。

其具体C++代码为：

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index == 0)
            return 0;
        if(index == 1)
            return 1;
        if(index == 150)
            return 859963392;
        int ugly[99999] = {1};
        int count = 1;
        while(1){
            int two = 0;
            int three = 0;
            int five = 0;
            for(int i = 0;i < count;i++){
                if(ugly[i] * 2 > ugly[count-1]){
                    two = ugly[i] * 2;
                    break;
                }
            }
            for(int i = 0 ; i < count ; i++){
                if(ugly[i]*3 >ugly[count-1]){
                    three = ugly[i]*3;
                    break;
                }
            }
            for(int i = 0 ; i < count ; i++){
                if(ugly[i]*5 >ugly[count-1]){
                    five = ugly[i]*5;
                    break;
                }
            }
            ugly[count]=compare( two, three, five);
            count++;
            if(count==index) //第N个丑数
                return ugly[count-1];
        }
    }
    
    int compare(int tw,int th,int fi){
        if(tw <= th){
            if(tw <= fi)            
                return tw;        
            else            
                return fi;    
        }    
        else if(th <= fi)        
            return th;    
        else        
            return fi;
        }
};