面试题34：丑数

面试题34：丑数

题目

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

暴力解法

从1开始步长为1，逐个判断是否为丑数。效率太低

根据丑数的规则，直接生成丑数序列

假如我们已经有了从1到k的丑数，如何生成k到N的丑数呢？

问题就在于第k+1个丑数是怎么生成的？

一个想法是从第一个丑数开始，依次乘以2、3、5，直到出现大于第k个丑数。

但这样又有很多不必要的计算。

假设我们从第一个丑数开始，依次乘以2、3、5，直到出现大于第k个丑数，此时这个位置能否直接用于第k+2个数的生成呢？而不是每次都从第一个丑数开始计算。

顺着这个思路比较难想清楚。换个思路

每个丑数的出现必定是前面的丑数乘以2或者3或者5。我们先对前面的每个丑数都依次乘以2，直到遇到大于第k个丑数的情况，并记下这个位置；然后对前面的每个丑数都依次乘以3，直到遇到大于第k个丑数的情况，并记下这个位置；然后对前面的每个丑数依次乘以5，直到遇到大于第k个丑数的情况，并记下这个位置。这样我们就有了三个大于第k个丑数的新的丑数，那么谁是第k+1个丑数呢？当然是三者中较小的那个。然后第k+2的丑数可以接着前面的工作来。

public int GetUglyNumber_Solution(int index) {
    ArrayList<Integer> result = new ArrayList<>();
    result.add(1);
    int nextUgly = 0;
    int index2 = 0;
    int index3 = 0;
    int index5 = 0;
    while(index!=result.size()){
        int min = result.get(index2)*2<result.get(index3)*3?result.get(index2)*2:result.get(index3)*3;
        min = min<result.get(index5)*5?min:result.get(index5)*5;
        result.add(min);
        nextUgly++;
        while(result.get(index2)*2<=result.get(nextUgly)){
            index2++;
        }
        while (result.get(index3)*3<=result.get(nextUgly)){
            index3++;
        }
        while (result.get(index5)*5<=result.get(nextUgly)){
            index5++;
        }
    }
    return result.get(index-1);
}

用三个指针的好处就是可以记录进度，想用一个指针完成记录进度的工作是不可能的。