丑数.md

题目描述

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

测试用例

• 功能测试（输入2、3、4、5、6等）
• 特殊输入测试（边界值1；无效输入0）
• 性能测试（输入较大的数字，如1500）

题目考点

• 考察应聘者对时间复杂度的理解。
• 考察应聘者的学习能力和沟通能力，当应聘者听到不熟悉的概念之后，要有主动积极的态度，大胆向面试官提问。

解题思路

自己解题为什么超时？是因为不管一个数是不是丑数，我们都需要对它进行计算，所以我们试着找到一种只计算丑数的方法。

根据丑数的定义，丑数应该是另一个丑数乘以2、3或者5的结果（1除外），因此我们可以创建一个数组，里面的数字都是排好序的丑数，每个丑数都是前面的丑数乘以2、3或者5得到的。（这些需要思考一下🤔）

自己解题

/**
 * 丑数
 *
 * @Author rex
 * 2018/9/1
 */
public class Solution {
    /**
     * 求出第index个丑数
     * @param index
     * @return
     */
    public int getUglyNumber_Solution(int index) {
        // 防止特殊输入
        if (index <= 0) {
            return 0;
        }

        int count = 0;
        int base = 0;
        while (count != index) {
            base++;
            if (isUglyNumber(base)) {
                count++;
            }
        }
        return base;

    }

    /**
     * 判断是否为丑数
     * @param number
     * @return
     */
    boolean isUglyNumber(int number) {
        while (number % 2 == 0) {
            number /= 2;
        }
        while (number % 3 == 0) {
            number /= 3;
        }
        while (number % 5 == 0) {
            number /= 5;
        }
        return number == 1;
    }


}

不足：

超过了时间限制(太多尝试计算)

参考解题

/**
 * 丑数
 *
 * @Author rex
 * 2018/9/1
 */
public class Solution1 {
    /**
     * 求出第index个丑数
     * 空间换时间
     *
     * @param index
     * @return
     */
    public int getUglyNumber_Solution(int index) {
        // 防止特殊输入
        if (index <= 0) {
            return 0;
        }
        // 存放所有丑数
        int[] dp = new int[index];
        dp[0] = 1;
        int nextUglyIndex = 1;
        // 存储乘以2、3、5的下标（当一个数乘完，下标加1）
        int i2 = 0, i3 = 0, i5 = 0;

        // 保证数组都是排序且都是由前面丑数得来的
        while (nextUglyIndex < index) {
            int min = Math.min(dp[i2] * 2, Math.min(dp[i3] * 3, dp[i5] *5));
            dp[nextUglyIndex] = min;
            if (dp[i2] * 2 == min) {
                i2++;
            }
            if (dp[i3] * 3 == min) {
                i3++;
            }
            if (dp[i5] * 5 == min) {
                i5++;
            }
            nextUglyIndex++;
        }
        return dp[index - 1];
    }

}

补充

空间和时间要求可以咨询面试官