一、题目

给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

提示：

• 1 <= n <= 1690

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ugly-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、分析及代码

1. 动态规划

（1）思路

每一个丑数都是由更小的丑数乘以 2、3 或 5 得到的，因此可设计 3 个指针分别记录各质因数当前对应被乘数的所在位置，每次选取相乘后最小的数加入数组，并移动指针，直至得到第 n 个丑数。

（2）代码

class Solution {public int nthUglyNumber(int n) {int[] nums = new int[n];//丑数数组nums[0] = 1;int i2 = 0, i3 = 0, i5 = 0;//质因数2、3、5对应的指针int num2 = nums[i2] * 2, num3 = nums[i3] * 3, num5 = nums[i5] * 5;//质因数2、3、5与指针位置丑数相乘后对应的数for (int i = 1; i < n;) {int lastNum = nums[i - 1];//上一个添加的丑数，用于去重if (num2 <= num3 && num2 <= num5) {//乘2对应的数最小nums[i++] = num2;num2 = nums[++i2] * 2;} else if (num3 < num2 && num3 <= num5) {//乘3对应的数最小if (num3 != lastNum)//有可能与上次乘2对应的数相同，去重nums[i++] = num3;num3 = nums[++i3] * 3;} else {if (num5 != lastNum)//乘5对应的数最小nums[i++] = num5;//有可能与上次乘2或3对应的数相同，去重num5 = nums[++i5] * 5;}}return nums[n - 1];//第n个丑数}
}

（3）结果

执行用时 ：3 ms，在所有 Java 提交中击败了 81.63% 的用户；
内存消耗 ：37.5 MB，在所有 Java 提交中击败了 65.94% 的用户。

三、其他

暂无。