剑指offer——丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

 

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:  

1 是丑数。
n 不超过1690。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/chou-shu-lcof

题目对丑数的概念很简短，可能一时间看不明白。

因子：现在有n*m=p,则n和m是p因子。比如2*6=12,那么2和6就是12的因子。
质数：一个数的因子只有1和这个数本身，那么这个数就是质数。比如2的因子只有1和2；5的因子只有1和5；所以2，5是质数。

丑数：有质因子2,3,5，丑数=小丑数*（2或3或5），丑数的因子分解出来可以全是2,3,5。比如12=2*2*3，10=2*5，9=3*3*3。公式为：2^x*3^y*5^z

解题思路：
由上面的说法可以想出一种简单方法来判断一个数number是否是丑数：
将number循环除以2，直到不能整除。
再将得到的商分别循环除以3,5，如果最后能够整除，且商为1，那么这个数是丑数。

例如：
12/2=6 6/2=3 3/2=1...1（有余数1，换3） 3/3=1 （符合条件，为丑数）
14/2=7 7/2=3...1 (有余数，换3) 7/3=2...1 (有余数,换5) 7/5=1...2 (不符合条件，不是丑数)

判断丑数代码如下：

var isUgly=function(num){

        while(num%2==0)
        num=num/2;

        while(num%3==0)
        num=num/3;

        while(num%5==0)
        num=num/5;

    return ( num===1)?true:false;
}

要找出第n个丑数，那么可以选择遍历

解1

var isUgly=function(num){

        while(num%2==0)
        num=num/2;

        while(num%3==0)
        num=num/3;

        while(num%5==0)
        num=num/5;

    return ( num===1)?true:false;
}

var nthUglyNumber = function(n) {
    if(n<=0)
    return 0;
    
    var index=0;
    var current=0;
    while(index<n){
        current++;
        if(isUgly(current)){
            index++;
        }
        
    }

    return current;


};

这样的方法理解起来比较容易，但是明显的缺点就是时间消耗比较大，每个数都要判断是不是丑数，然后我们要找第1600个丑数呢？那么我们将会判断上亿个数字是否为丑数。

下面有一种是靠空间换时间的方法，是剑指offer书上提供的方法。具体解析参考书上的解释。

解题思路：

如果我们将已经找到的丑数按从小到大的方式有序的存入数组uglyArr。现在知道的最大丑数为M，我们需要找到下一个丑数。下一个丑数M_NEXT应该是当前uglyArr数组中的某个丑数的2倍，3倍或者5倍。我们可以将uglyArr数组中的数都变成2倍，3倍或5倍。他们都是丑数，但是我们要找的M_next是大于M的丑数中最小的那一个。比如现在uglyArr=[1,2,3,4,5]，M=5，我们现在找Mnext。

2倍：uglyArr*2=[2,4,6,8,10]

3倍：uglyArr*3=[3,6,9,12,15]

5倍：uglyArr=[5,10,15,20,25]

比5大的数：6,8,10,12,15,20,25。M_next是大于M的丑数中最小的那一个_，M_next=6。这样就找到了下一个丑数。

我们还可以继续优化，因为uglyArr数组中有些数是可以在2,3,5倍时只比M大一点点，我们只需要找出这个临界的数即可，设为t2,t3,t5。 就如上面例子中，t2=3，t3=2，t5=2，t2*2=6, t3*3=6，t5*5=10。6,6,10相比，最小为6。

解2

var minNum=function(a,b,c){
    return a<b?(a<c?a:c):(b<c?b:c)
}
var nthUglyNumber = function(n) {
    //如果小于等于0,那么可以直接返回0
    if(n<=0)
    return 0;
    
    var uglyArr=[1];//初始化丑数数组，这将是一个有序的丑数数组
    var currentIndex=1;//当前要寻找的丑数在数组中的索引位置
    
    //t2,t3,t5代表*2，*3，*5刚好大于或等于当前丑数数组中最大的丑数，最开始初始化为1
    var t2=1;
    var t3=1;
    var t5=1;
    

    while(currentIndex<n){
        var min=minNum(t2*2,t3*3,t5*5);//下一个丑数是t2*2,t3*3,t5*5中最小的
        uglyArr.push(min);

        //寻找临界值
        var temp=0;
        while(uglyArr[temp]*2<=min)
        temp++;

        t2=uglyArr[temp];

        temp=0;
        while(uglyArr[temp]*3<=min)
        temp++;

        t3=uglyArr[temp];

        temp=0;
        while(uglyArr[temp]*5<=min)
        temp++;

        t5=uglyArr[temp];

        currentIndex++;


    }

    return uglyArr[currentIndex-1];

};

也可以用动态规划的方法来实现，参考https://leetcode-cn.com/problems/chou-shu-lcof/solution/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t/,这里写的解释很详细，图文并茂，我这里用javascript来实现

解3

var minNum=function(a,b,c){
    return a<b?(a<c?a:c):(b<c?b:c)
}
var nthUglyNumber = function(n) {
    if(n<=0)
    return 0;
    
   var a=0,
   b=0,
   c=0;//三个位置

   var dp=[1]

   for(var i=0;i<n;i++){
        var min=minNum(dp[a]*2,dp[b]*3,dp[c]*5);
        dp.push(min)
        while(dp[a]*2<=min)
            a++;
        while(dp[b]*3<=min)
            b++;
        while(dp[c]*5<=min)
            c++;
   }

   return dp[n-1];

};