[每日一道小算法（十五）] [穷举] 丑数（剑指offer习题）

╰+攻爆jí腚メ 2023-07-04 08:55 19阅读 0赞

前言：  
最近也在看剑指offer上面的习题，有些思路很新奇，所以就再次做一下记录。

### 题目描述 ###

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

### 解题思路 ###

#### 方法一 ####

根据题意，我们可以看出一个数如果能被2整除，那么久连续除以2，如果能被3整除，那么就连续除以三，如果能被5整除，那么就连续出以5，最后如果该数等于1，那么这个数就是丑数。根据这个我们就可以从1开始，依次找出丑数，当找到1500个丑数的时候，结束查找，并返回。这种方法不好处就在于，不是丑数也会被一直做判断，所以时间效率不高。一会会在下面写出该例子。

#### 方法二 ####

我们知道，一个丑数，它乘以2，3，5以后，他仍然是一个丑数，所以我们可以用到这个特点来解决这个问题，建一个数组，然后将丑数从小到大进行排序。有了这个思路，我们就要开始考虑该怎么实现这个排序。我们从第一个丑数1开始，让他依次乘以2、3、5，将会得到2，3，5。通过比较将最小值2保存到数组中，然后将这个最小值2乘以2，3，5，得到4，6，10，再通过比较将最小值4保存到数组当中，接着保持这样下去。如果只是这么做，我们会发现一个问题，有些丑数我们把它错过了，没有保存到数组中，所以我们需要做一个优化。  
看一下优化以后的实现。第一次我们从第一个丑数1开始，让他依次乘以2，3，5，将会得到2，3，5，将最小值2保存下来到数组中，然后记录一下此时最小值是乘以2的得到的最小值。接下来，我们接着执行，丑数1乘以3，5得到3，5，最小值2乘以2，得到4，将这三个数进行比较，得出最小值是3，所以保存到数组中，然后记录一下此时最小值是乘以3的得到的最小值。接下来我们接着执行，这样就完美将这些丑数从下到达进行了排序。  
可能我的表述不是很好，下面我会贴出来样例代码，一看你们就懂了。

### 代码样例 ###

#### 方法一 ####

package com.asong.leetcode.UglyNum;
    
    /** * 丑数：下面这是一个个不好的解决办法，但是想起来很简单 * isUgly 用来判断这个数是不是丑数：如果他能被2整除，就一直除，如果能被3整除，就一直除，如果能被5整出，就一直除，最后num变为1，则代表是丑数。 * GetUglyNumber_Solution 这里从1开是一个一个的判断是不是丑数，并保存最大值。 */
    public class Solution { 
        /** * 用来判断是不是丑数 * @param num 要判断的数字 * @return */
        public static boolean isUgly(int num)
        { 
            while(num % 2 == 0)
            { 
                num /= 2;
            }
            while(num % 3 == 0)
            { 
                num /= 3;
            }
            while (num % 5 == 0)
            { 
                num /= 5;
            }
            return (num==1)?true:false;
        }
    
        /** * 得到第index个丑数 * @param index * @return */
        public int GetUglyNumber_Solution(int index) { 
            if(index <= 0)
            { 
                return 0;
            }
            int number = 0; //从0开始的数字
            int uglyFound = 0; //找到的丑数计数 到达index截至
            while(uglyFound < index)
            { 
                ++number;
                if(isUgly(number))
                { 
                    uglyFound++;
                }
            }
    
            return number;
        }
    }

#### 方法二 ####

package com.asong.leetcode.UglyNum;
    
    import java.util.Vector;
    
    public class SolutionNice { 
        public int GetUglyNumber_Solution(int index) { 
            if(index <= 0)
            { 
                return 0;
            }
            int[] uglyNumbers = new int[index]; //创建数组保存丑数
            uglyNumbers[0] = 1; //第一个丑数
            int nextUglyIndex = 1; //作为索引
            int ugly2=0,ugly3=0,ugly5=0; //用来保存每个丑数的最小值在数组中的位置
            for (nextUglyIndex = 1 ;nextUglyIndex < index ; nextUglyIndex++)
            { 
                uglyNumbers[nextUglyIndex]=Math.min(uglyNumbers[ugly2]*2,Math.min(uglyNumbers[ugly3]*3,uglyNumbers[ugly5]*5));
                if(uglyNumbers[nextUglyIndex] == uglyNumbers[ugly2]*2)
                { 
                    ugly2++;
                }
                if(uglyNumbers[nextUglyIndex] == uglyNumbers[ugly3]*3)
                { 
                    ugly3++;
                }
                if(uglyNumbers[nextUglyIndex] == uglyNumbers[ugly5]*5)
                { 
                    ugly5++;
                }
            }
            return uglyNumbers[index-1];
        }
    }