题目描述
这是 LeetCode 上的264. 丑数 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
基本思路
根据丑数的定义,我们有如下结论:
- 111 是最小的丑数。
- 对于任意一个丑数 xxx,其与任意的质因数(222、333、555)相乘,结果(2x2x2x、3x3x3x、5x5x5x)仍为丑数。
优先队列(小根堆)解法
有了基本的分析思路,一个简单的解法是使用优先队列:
- 起始先将最小丑数 111 放入队列
- 每次从队列取出最小值 xxx,然后将 xxx 所对应的丑数 2x2x2x、3x3x3x 和 5x5x5x 进行入队。
- 对步骤 2 循环多次,第 nnn 次出队的值即是答案。
为了防止同一丑数多次进队,我们需要使用数据结构 SetSetSet 来记录入过队列的丑数。
代码:
class Solution { int[] nums = new int[]{2,3,5}; public int nthUglyNumber(int n) { Set<Long> set = new HashSet<>(); Queue<Long> pq = new PriorityQueue<>(); set.add(1L); pq.add(1L); for (int i = 1; i <= n; i++) { long x = pq.poll(); if (i == n) return (int)x; for (int num : nums) { long t = num * x; if (!set.contains(t)) { set.add(t); pq.add(t); } } } return -1; } } 复制代码
- 时间复杂度:从优先队列中取最小值为 O(1)O(1)O(1),往优先队列中添加元素复杂度为 O(logn)O(\log{n})O(logn)。整体复杂度为 O(nlogn)O(n\log{n})O(nlogn)。
- 空间复杂度:O(n)O(n)O(n)。
多路归并(多指针)解法
从解法一中不难发现,我们「往后产生的丑数」都是基于「已有丑数」而来(使用「已有丑数」乘上「质因数」222、333、555)。
因此,如果我们所有丑数的有序序列为 a1,a2,a3,...,ana1,a2,a3,...,ana1,a2,a3,...,an 的话,序列中的每一个数都必然能够被以下三个序列(中的至少一个)覆盖:
- 由丑数 * 222 所得的有序序列:1∗21 * 21∗2、2∗22 * 22∗2、3∗23 * 23∗2、4∗24 * 24∗2、5∗25 * 25∗2、6∗26 * 26∗2、8∗28 * 28∗2 ...
- 由丑数 * 333 所得的有序序列:1∗31 * 31∗3、2∗32 * 32∗3、3∗33 * 33∗3、4∗34 * 34∗3、5∗35 * 35∗3、6∗36 * 36∗3、8∗38 * 38∗3 ...
- 由丑数 * 555 所得的有序序列:1∗51 * 51∗5、2∗52 * 52∗5、3∗53 * 53∗5、4∗54 * 54∗5、5∗55 * 55∗5、6∗56 * 56∗5、8∗58 * 58∗5 ...
举个🌰,假设我们需要求得 [1,2,3,...,10,12][1, 2, 3, ... , 10, 12][1,2,3,...,10,12] 丑数序列 arrarrarr 的最后一位,那么该序列可以看作以下三个有序序列归并而来:
- 1∗2,2∗2,3∗2,...,10∗2,12∗21 * 2, 2 * 2, 3 * 2, ... , 10 * 2, 12 * 21∗2,2∗2,3∗2,...,10∗2,12∗2 ,将 222 提出,即 arr∗2arr * 2arr∗2
- 1∗3,2∗3,3∗3,...,10∗3,12∗31 * 3, 2 * 3, 3 * 3, ... , 10 * 3, 12 * 31∗3,2∗3,3∗3,...,10∗3,12∗3 ,将 333 提出,即 arr∗3arr * 3arr∗3
- 1∗5,2∗5,3∗5,...,10∗5,12∗51 * 5, 2 * 5, 3 * 5, ... , 10 * 5, 12 * 51∗5,2∗5,3∗5,...,10∗5,12∗5 ,将 555 提出,即 arr∗5arr * 5arr∗5
因此我们可以使用三个指针来指向目标序列 arrarrarr 的某个下标(下标 000 作为哨兵不使用,起始都为 111),使用 arr[下标]∗质因数arr[下标] * 质因数arr[下标]∗质因数 代表当前使用到三个有序序列中的哪一位,同时使用 idxidxidx 表示当前生成到 arrarrarr 哪一位丑数。
代码:
class Solution { public int nthUglyNumber(int n) { // ans 用作存储已有丑数(从下标 1 开始存储,第一个丑数为 1) int[] ans = new int[n + 1]; ans[1] = 1; // 由于三个有序序列都是由「已有丑数」*「质因数」而来 // i2、i3 和 i5 分别代表三个有序序列当前使用到哪一位「已有丑数」下标(起始都指向 1) for (int i2 = 1, i3 = 1, i5 = 1, idx = 2; idx <= n; idx++) { // 由 ans[iX] * X 可得当前有序序列指向哪一位 int a = ans[i2] * 2, b = ans[i3] * 3, c = ans[i5] * 5; // 将三个有序序列中的最小一位存入「已有丑数」序列,并将其下标后移 int min = Math.min(a, Math.min(b, c)); // 由于可能不同有序序列之间产生相同丑数,因此只要一样的丑数就跳过(不能使用 else if ) if (min == a) i2++; if (min == b) i3++; if (min == c) i5++; ans[idx] = min; } return ans[n]; } } 复制代码
- 时间复杂度:O(n)O(n)O(n)。
- 空间复杂度:O(n)O(n)O(n)。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.264
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。