图解LeetCode——剑指 Offer 49. 丑数

一、题目

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

二、示例

2.1> 示例:

【输入】 n = 10 【输出】 12 【解释】 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:  

• 1 是丑数。
• n 不超过1690。

三、解题思路

根据题意，我们要获取从小到大顺序的第n个丑数，那么对于任意一个丑数，其计算公式就是：2的x次方 * 3的y次方 * 5的z次方（x，y，z分别表示数字2、3、5的出现次数）；

针对以上逻辑，我们就针对数字2、数字3和数字5创建3个指针，分别为：index2、index3和index5；

由于1就是丑数，所以，当我们创建待返回结果数组result之后，就可以直接将第一个元素赋值为1了，即：result[0]=1，然后进行如下计算逻辑：

【针对数字2】计算2*index2的值，如果是最小值，则将该值保存到result数组中，并且执行index2++； 【针对数字3】计算3*index3的值，如果是最小值，则将该值保存到result数组中，并且执行index3++； 【针对数字5】计算5*index5的值，如果是最小值，则将该值保存到result数组中，并且执行index5++；

针对上面的逻辑计算，当满足result的长度等于n的时候，则返回result[n-1]就是这道题所要获得的第n个丑数了。

如上就是本题的解题思路了，下面我们还是依照惯例，通过例子来演示一下。由于篇幅问题，下面我只画出了result中的第4个元素的构造过程，不过对于整体解题思路的理解是没有任何影响的。具体请见下图所示：

四、代码实现

class Solution {
    public int nthUglyNumber(int n) {
        int index2 = 0, index3 = 0, index5 = 0;
        int[] result = new int[n];
        result[0] = 1;
        for(int i = 1; i < n; i++) {
            int minValue = Math.min(Math.min(2 * result[index2], 3 * result[index3]), 5 * result[index5]);
            if (minValue == 2 * result[index2]) index2++;
            if (minValue == 3 * result[index3]) index3++;
            if (minValue == 5 * result[index5]) index5++;
            result[i] = minValue;
        } 
        return result[n - 1];
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」