丑数

题目描述

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

这里说的因子其实指的是质因子，比如8含有因子4，但4不是质因子，8的质因子为2。

解法一：

最直观暴力的解题思路就是碰到一个数字，便去检测它是不是丑数，若是则记录下来，否则继续检测下一个数。
代码如下：

public class Solution {
    public static int GetUglyNumber_Solution(int index) {
        int n = 1;
        int i = 1;
        while(i != index) {
            n++;
            if(isUgly(n)) {
                i++;
            }
        }
        return n;
         
    }
    public static boolean isUgly(int num) {
        while(num % 2 == 0)
            num /= 2;
        while(num % 3 == 0)
            num /= 3;
        while(num % 5 == 0)
            num /= 5;
        if(num == 1)
            return true;
        else
            return false;
    }
}

但是这种方法时间性能很差，如果两个丑数之间距离较大，会产生很多无意义计算，最终导致超时。

解法二：

由于丑数的因子只包含2、3、5，那么一个丑数m必定由一个更小的丑数n乘上因子（n * 2或n * 3或n * 5)得到，也就是说，通过递推可以得到之后的丑数，那么我们便可以只计算丑数，比解法一减少了很多工作量。

    起始的第一个丑数是1，通过1*2，1*3，1*5我们可以得到三个丑数，但是数组中的丑数需要升序排列，所以我们只能先在数组中放入最小的2， 得到[1，2]。
    由于第一个数乘以2已经被遍历过了，按照递推，丑数序列中乘以2后值最小的只能是第二个数（已乘以2的不计）。所以我们将指针s2置为1，指向第二个数。由于第一个数可以生成的三个丑数只放入了一个乘以2得到的，那么s3和s5依旧为0，指向第一个数。
    将2*2，1*3，1*5进行比较，取最小的1*3，得到[1，2，3]，第一个数的乘以3也被遍历到了，令s3 = 1指向第二数。s2依旧为1，s5为0。
    ……
    我们每一次都是取最小的值放入，然后更新其指针。如果最小的值出现重复怎么办（如array[s1]*2 == array[s5]*5），这时应该向数组中放入该值后，s1和s5均更新，相当于这两个值均放进了数组，只不过是用一个位置，这样就可以保证数组中的数字无重复。
    看到这里我们可以总结发现，s2、s3和s5实质上就是用来记录每一个已经得到的丑数可推导出的三个丑数，通过s2、s3和s5的移动，数组中已有的每一个丑数的三个递推丑数均得到了遍历。通过取最小值和相同值合并实现数组的递推有序增长。

public class Solution {
    public static int GetUglyNumber_Solution(int index) {
        if(index <= 0)
            return 0;
        int s2 = 0, s3 = 0, s5 = 0;
        int[] result = new int[index];
        result[0] = 1;
        for(int i = 1; i < index; i++) {
            result[i] = Math.min(result[s2] * 2, Math.min(result[s3] * 3, result[s5] * 5));
            if(result[i] == result[s2] * 2)
                s2++;
            if(result[i] == result[s3] * 3)
                s3++;
            if(result[i] == result[s5] * 5)
                s5++;
        }
        return result[index - 1];
    }
    
}

解法三：

这是在剑指 offer上的解法，实质计算过程与解法二相同，但是可以从另一个角度来理解。
假设已有的最大丑数为M，记要生成的下一个丑数为N。则N一定是之前的某一个丑数乘以2、3或5的结果。
遍历之前的丑数，将其均乘以2，由于数组是有序的，则一定存在一个结果首先大于M，记为X2；
遍历之前的丑数，将其均乘以3，由于数组是有序的，则一定存在一个结果首先大于M，记为X3；
遍历之前的丑数，将其均乘以5，由于数组是有序的，则一定存在一个结果首先大于M，记为X5；
由于数组是有序的，新插入的数字一定是递推生成的丑数中最小的，则必在X2，X3，X5中。（因为X2是乘以2生成的大于M的最小值，X3，X5同理）
取最小值后更新指针。

public class Solution {
    public static int GetUglyNumber_Solution(int index) {
        if(index <= 0)
            return 0;
        int s2 = 0, s3 = 0, s5 = 0;
        int[] result = new int[index];
        result[0] = 1;
        for(int i = 1; i < index; i++) {
            result[i] = Math.min(result[s2] * 2, Math.min(result[s3] * 3, result[s5] * 5));
            while(result[s2] * 2 <= result[i])
                s2++;
            while(result[s3] * 3 <= result[i])
                s3++;
            while(result[s5] * 5 <= result[i])
                s5++;
        }
        return result[index - 1];
    }
    
}