丑数

题目来源

• 来源：力扣264

题目描述

描述：

​ 编写一个程序，找出第 n 个丑数。

​ 丑数就是只包含质因数 2, 3, 5 的正整数。

​ 例如：15是3*5，9是3*3，15和9都是丑数

示例:

​ 输入: n = 10
​ 输出: 12
解释:

​ 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:

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

解法分析

• 题目要求：第k个丑数。所以我们需要求丑数的升序序列的获取方式。

首先，分析丑数的获取方式

• 由第一个丑数1，分别于三个质因数相乘，得到三个丑数，然后排序，得到1、2、3、5.
• 然后对第二个丑数2，再次进行一步骤的操作，得到丑数4、6、10.升序排列得到1、2、3、4、5、6、10.
• 再对第三个丑数进行一步骤的操作，再对整体的数列进行排序，即可得到新的丑数序列。
• 丑数既然可以通过这种方式获得，针对题目要求，可以进行一些修改，即可得到第k个丑数。

实现方式思路如下，这里举个例子

• 对于第一个质因数，分别和2、3、5相乘，取到最小的2，作为第二个质因数，然后，由于1已经和质因数2相乘得到丑数，这时，1不需要和质因数2再做乘法操作来获取丑数
• 所以，第二次操作，就是1和3、5相乘，而质因数2和第二个丑数相乘，取到最小的3作为第三个丑数，然后，由于1已经和质因数3相乘得到丑数，这时，1不需要和质因数3再做乘法操作来获取丑数
• 所以，第三次操作，就是1和5相乘，而质因数2、3和第二个丑数相乘，取到最小的4作为第四个丑数，然后，由于2已经和质因数2相乘得到丑数，这时，2不需要和质因数2再做乘法操作来获取丑数
• 依次类推，即可依次得到丑数序列。

图解

丑数.png

算法实现

• 由于需要分别标记质因数2、3、5分别和第几个丑数进行乘法运算，所以，可以定义三个指针对应三个质因数，指向数组中的位置。
• 这样，每次判断出，取到的值是和某个质因数反应，就可以将该质因数对应的指针向后移动一位。

代码实现（Java）

public int nthUglyNumber(int n) {
        //定义一个数组存储丑数序列
        int[] dp = new int[n];
        dp[0] = 1;
        int min = Integer.MAX_VALUE;
        //定义三个指针，分别对应质因数2、3、5.
        int i2 = 0,i3 = 0,i5 = 0;
        for (int i = 1; i < n; i++) {
            //取得最小值作为下一个丑数
            min = Math.min(dp[i2] * 2,Math.min(dp[i5] * 5,dp[i3] * 3));
            //判断是那一个质因数参与得到丑数，将其指针向后移动一位
            if(min == dp[i3] * 3) i3++;
            if(min == dp[i5] * 5) i5++;
            if(min == dp[i2] * 2) i2++;
            //将丑数存入丑数序列
            dp[i] = min;
        }
        return dp[n - 1];
    }