丑数 II

难度:

标签:

题目描述

给你一个整数 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

代码结果

运行时间: 29 ms, 内存: 16.0 MB

// Using Java Stream to generate the nth ugly number involves using a TreeSet to maintain
// the order of generated ugly numbers. We use the set to avoid duplicates and always get the
// smallest element.
 
import java.util.*;
import java.util.stream.*;
 
public class UglyNumberStream {
    public int nthUglyNumber(int n) {
        Set<Long> uglyNumbers = new TreeSet<>();
        uglyNumbers.add(1L);
        long ugly = 1;
 
        for (int i = 0; i < n; i++) {
            ugly = uglyNumbers.iterator().next();
            uglyNumbers.remove(ugly);
            uglyNumbers.add(ugly * 2);
            uglyNumbers.add(ugly * 3);
            uglyNumbers.add(ugly * 5);
        }
 
        return (int) ugly;
    }
}

解释

方法:

该题解采用动态规划的思路，使用三个指针 i2、i3、i5 分别记录当前应该乘以 2、3、5 的丑数的下标。通过比较 arr[i2]*2、arr[i3]*3 和 arr[i5]*5 的大小，将最小的数添加到数组 arr 中，并递增对应的指针。最终返回 arr[n-1] 即为第 n 个丑数。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在动态规划的过程中，为什么需要三个指针i2、i3、i5分别跟踪乘以2、3、5的指数，而不能简单地每次乘以2、3、5然后选择最小值？

▷

使用三个指针i2、i3、i5的目的是为了确保每次生成的丑数是按顺序递增的，同时避免重复计算和重复添加。如果每次简单地对数组中的每个元素乘以2、3、5，然后选择最小值，这会导致计算效率低（因为很多乘积是重复的），且可能会重复添加相同的丑数，打破丑数递增的顺序。使用指针可以精确地控制每个基数（2、3、5）乘以合适的前一个丑数，确保每次添加的丑数都是当前未出现过的最小丑数。

🦆

题解中提到的while循环用于更新指针位置，具体是如何判断这些指针应该何时增加，以确保生成的序列是按顺序的？

▷

while循环确保指针i2、i3、i5总是指向尚未乘以2、3、5的最小丑数。在循环中，如果指针对应的乘积小于或等于当前数组中的最大丑数（arr[-1]），则表明这个乘积已经被添加过了或者不是下一个最小丑数，因此指针需要向前移动到下一个位置。这样，每个指针始终对应于还未被乘以其对应因子产生新丑数的位置，保证了丑数的正确顺序和唯一性。

🦆

如果在数组中出现了重复的丑数，题解中的方法是如何避免重复添加相同的丑数进入数组的？

▷

通过同时比较三个不同指针（i2、i3、i5）对应的乘积（a2、a3、a5）并选取其中的最小值，题解中的方法可以避免重复。如果两个或三个乘积相等，只有其中的最小值被添加到数组中，而所有等于这个最小值的乘积对应的指针都会被递增。这样可以确保每个新添加的丑数都是唯一的，并且是当前尚未添加过的最小丑数。

🦆

在当前的题解逻辑中，如果n非常大，例如靠近1690的上限，这种算法处理大数据量的效率如何？是否会有性能瓶颈？

▷

该算法的时间复杂度主要取决于n的大小，因为每次迭代都涉及计算三个乘积并更新数组和指针。随着n的增大，数组和每次迭代的计算量也增加，但由于每次迭代只处理三个计算和一些比较操作，其时间复杂度为O(n)，空间复杂度也为O(n)，这在实际中通常是可接受的。但是，如果n非常大，例如接近整型上限，这种算法的内存使用量会成为一个瓶颈，因为它需要存储所有计算出的丑数。

相关问题

合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

提示：

0 <= n <= 5 * 10⁶

丑数

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

给你一个整数 n ，请你判断 n 是否为丑数。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：n = 6
输出：true
解释：6 = 2 × 3

示例 2：

输入：n = 1
输出：true
解释：1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。

示例 3：

输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。

提示：

-2³¹ <= n <= 2³¹ - 1

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 10⁴

超级丑数

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

示例 1：

输入：n = 12, primes = [2,7,13,19]
输出：32 
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

示例 2：

输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。

提示：

1 <= n <= 10⁵
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ，且按 递增顺序 排列

丑数粉刷房子 II