丑数

题目：

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

分析：

1. 逐个判断每个数字是不是丑数，直观但不够高效

   所谓一个丑数 m 是另一个数 n 的因子，是指 n 能被 m 整除，也就是 n%m ==0。根据丑数的定义，丑数只能被2、3、5 整除。也就是说，如果一个数能被 2 整除，就连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就连续除以5。如果最后得到的是 1，那么这个数就是丑数；否则不是。

   根据上面思路，可以得到如下代码：

   class Solution {
   
       boolean isUgly(int number) {
           while (number % 2 == 0) {
               number /= 2;
           }
           while (number % 3 == 0) {
               number /= 3;
           }
           while (number % 5 == 0) {
               number /= 5;
           }
           return number == 1;
       }
   
       int getUglyNumber(int count) {
           if (count <= 0) {
               return 0;
           }
           int number = 0;
           int uglyFound = 0;
           while (uglyFound < count) {
               ++number;
               if (isUgly(number)) {
                   ++uglyFound;
               }
           }
           return number;
       }
   
       public static void main(String[] args) {
           long start = System.currentTimeMillis();
           Solution solution = new Solution();
           int uglyNumber = solution.getUglyNumber(1500);
           System.out.println(uglyNumber);
           System.err.println(System.currentTimeMillis()-start);
       }
   }
   

   

   耗时基本在 9000ms 左右，还是比较慢的。

   该算法非常直观，代码也非常简洁，但最大的问题就在于每个整数都需要计算。即使一个数字不是丑数，我们还是需要对它做求余数和除法操作。因此该算法的时间效率不是很高，

2. 创建数组保存已经找到的丑数，用空间换时间的解法

   • 根据丑数的定义，我们可以知道丑数可以由另外一个丑数乘以2，3或者5得到。因此，我们可以创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以2，3或者5得到的。
   • 我们把得到的第一个丑数乘以2以后得到的大于M的结果记为M2。同样，我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么M后面的那一个丑数应该是M2，M3和M5当中的最小值：Min(M2,M3,M5)。比如将丑数数组中的数字按从小到大乘以2，直到得到第一个大于M的数为止，那么应该是2x2=4<M，3x2=6>M，所以M2=6。同理，M3=6，M5=10。所以下一个丑数应该是6。

   根据上面思路，可以得到如下代码：

   class Solution2 {
       int getUglyNumber(int count) {
           if (count <= 0) {
               return 0;
           }
           int[] uglyNumbers = new int[count];
           uglyNumbers[0] = 1;
           int nextUglyIndex = 1;
   
           int multiply2 = 0;
           int multiply3 = 0;
           int multiply5 = 0;
   
           while (nextUglyIndex < count) {
               int min = min(uglyNumbers[multiply2] * 2, uglyNumbers[multiply3] * 3, uglyNumbers[multiply5] * 5);
               uglyNumbers[nextUglyIndex] = min;
   
               while (uglyNumbers[multiply2] * 2 <= uglyNumbers[nextUglyIndex]) {
                   multiply2++;
               }
               while (uglyNumbers[multiply3] * 3 <= uglyNumbers[nextUglyIndex]) {
                   multiply3++;
               }
               while (uglyNumbers[multiply5] * 5 <= uglyNumbers[nextUglyIndex]) {
                   multiply5++;
               }
               nextUglyIndex++;
           }
   
           return uglyNumbers[count - 1];
       }
   
       private int min(int number1, int number2, int number3) {
           int min = Math.min(number1, number2);
           return Math.min(min, number3);
       }
   
       public static void main(String[] args) {
           long start = System.nanoTime();
           Solution2 solution2 = new Solution2();
           int uglyNumber = solution2.getUglyNumber(1500);
           System.out.println(uglyNumber);
           System.err.println(System.nanoTime()-start);
       }
   }
   

   

   耗时不到 1ms，速度非常快。

   和第一种方案相比，第二种方案不需要在非丑数的整数上做任何计算，因此时间效率有明显提升。但也需要指出，第二种算法由于需要保存已经生成的丑数，因此需要一个数组，从而增加了空间消耗。如果是求第1500个丑数，将创建一个能容纳1500个丑数的数组，这个数组占内存6KB。