跳至主要內容

264. 丑数 II


264. 丑数 II

🟠   🔖  哈希表 数学 动态规划 堆(优先队列)  🔗 力扣open in new window LeetCodeopen in new window

题目

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丑数

说明:丑数是只包含质因数 23 和/或 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+🔴🀄️open in new window 🔗open in new window
204计数质数数组 数学 枚举 1+🟠🀄️open in new window 🔗open in new window
263丑数数学🟢🀄️open in new window 🔗open in new window
279完全平方数[✓]广度优先搜索 数学 动态规划🟠🀄️open in new window 🔗open in new window
313超级丑数数组 数学 动态规划🟠🀄️open in new window 🔗open in new window
1201丑数 III数学 二分查找 组合数学 1+🟠🀄️open in new window 🔗open in new window