0264.md

title	description	keywords
264. 丑数 II	LeetCode 264. 丑数 II题解，Ugly Number II，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 264. 丑数 II 丑数 II Ugly Number II 解题思路 哈希表 数学 动态规划 堆（优先队列）

264. 丑数 II

🟠 Medium  🔖  哈希表 数学 动态规划 堆（优先队列）  🔗 力扣 LeetCode

题目

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

Example 1:

Input: n = 10

Output: 12

Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Example 2:

Input: n = 1

Output: 1

Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Constraints:

• 1 <= n <= 1690

题目大意

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

说明：丑数是只包含质因数 2、3 和/或 5 的正整数；1 是丑数。

解题思路

这道题很精妙，你看着它好像是道数学题，实际上它却是一个合并多个有序链表的问题，同时用到了筛选素数的思路。

类似 如何高效寻找素数 的思路：如果一个数 x 是丑数，那么 x * 2, x * 3, x * 5 都一定是丑数。

我们把所有丑数想象成一个从小到大排序的链表，就是这个样子：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> ...

然后，我们可以把丑数分为三类：2 的倍数、3 的倍数、5 的倍数（按照题目的意思，1 算作特殊的丑数，放在开头），这三类丑数就好像三条有序链表，如下：

• 能被 2 整除的丑数：

1 -> 1*2 -> 2*2 -> 3*2 -> 4*2 -> 5*2 -> 6*2 -> 8*2 ->...

• 能被 3 整除的丑数：

1 -> 1*3 -> 2*3 -> 3*3 -> 4*3 -> 5*3 -> 6*3 -> 8*3 ->...

• 能被 5 整除的丑数：

1 -> 1*5 -> 2*5 -> 3*5 -> 4*5 -> 5*5 -> 6*5 -> 8*5 ->...

我们其实就是想把这三条「有序链表」合并在一起并去重，合并的结果就是丑数的序列，然后求合并后的这条有序链表中第 n 个元素是什么。

代码

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function (n) {
	let index2 = 0,
		index3 = 0,
		index5 = 0;
	let val2 = 1,
		val3 = 1,
		val5 = 1;
	let ugly = new Array(n);
	let index = 0;
	while (index < n) {
		let min = Math.min(val2, val3, val5);
		ugly[index] = min;
		index++;
		if (min == val2) {
			val2 = 2 * ugly[index2];
			index2++;
		}
		if (min == val3) {
			val3 = 3 * ugly[index3];
			index3++;
		}
		if (min == val5) {
			val5 = 5 * ugly[index5];
			index5++;
		}
	}
	return ugly[n - 1];
};

相关题目

题号	标题	题解	标签	难度	力扣
23	合并 K 个升序链表	[✓]	链表 分治 堆（优先队列） 1+	🔴	🀄️ 🔗
204	计数质数	[✓]	数组 数学 枚举 1+	🟠	🀄️ 🔗
263	丑数	[✓]	数学	🟢	🀄️ 🔗
279	完全平方数	[✓]	广度优先搜索 数学 动态规划	🟠	🀄️ 🔗
313	超级丑数	[✓]	数组 数学 动态规划	🟠	🀄️ 🔗
1201	丑数 III		数学 二分查找 组合数学 1+	🟠	🀄️ 🔗