- y总题解
-
看此题的基础 是 题解:lc 264. 丑数 II & 剑指 49. 丑数 。
- 知识点:c++ 优先队列 priority_queue 用法
题目
思路
- 这道题 只不过 把 题解:lc 264. 丑数 II & 剑指 49. 丑数 中
三路归并求min( )
的 操作 换成了多路归并用小根堆 求最小
,时间复杂度方面:小根堆 取最小值 O(1),插入元素调整 是 O(k)。
代码
- 看此题的基础 是 题解:lc 264. 丑数 II & 剑指 49. 丑数 。
1. 代码说明
-
宫水三叶 代码中 用的 是
三元组
,分别存val
,质数x
(质数x的在primes中的下标 i, x = primes[i],相当于存质数x)和质数x所属序列的指针当前的下标ptr
,三者有关系:val
=s[ptr(p0/p1/p2)...]
*x(P0/P1/P2...)
-
本代码 用的 是 二元组
pair
,所以只能 记录val
,质数x
,下标ptr
三者中的两个
。至于存储哪两个呢?有三种方案:-
如果存储
x
和ptr
,我们就不能用 小根堆 进行排序了,因为我们的小根堆 要根据val
值排序,本题相较于 lc 264. 丑数 II & 剑指 49. 丑数 而言 正是因为利用了 小根堆 对val
值进行排序,才将 时间复杂度 优化为 O(nlogm
). 所以val
,质数x
,下标ptr
三者中肯定要选val
。 -
如果存储
val
和x
,得到s[ptr]
,我们还需要去丑数序列s
中 看看到底 是哪个下标 i
对应的s[i] = s[ptr]
,然后才知道ptr = i
是多少,这样不是很方便。 -
只剩下存储
val
和ptr
了,通过 x =val
/s[ptr(p0/p1/p2)...]
来推出 x是 质数(P0/P1/P2…)中的哪一个,进而 得知 当前指针 ptr 是 指向 序列SP0/SP1/SP2
… 中的哪一个 -
利用
pair二元组
存储三种信息
,只能通过这种 推导关系,来得到需要的信息,所以 有点点绕
,需要想一下。c++ 中 好像也可以用 tuple元组 创建多元组,进而就可以 类似于宫水三叶 存储三种信息,省去 由两者推第三者的 步骤了,正所谓空间换时间hhh,有兴趣的可以尝试一下~
-
-
本代码中 各变量的 含义:
- m是 质数序列primes的长度:m = primes.size()
- s 表示丑数序列,要生成的丑数的个数 由题中给定,大小为 n。
vector<int> s(n)
; idx
表示当前生成丑数的下标
。一定要 明确 idx的定义 !!!和指针下标ptr
区分开来!- 序列
SP0/SP1/SP2
… 类似于 lc 264. 丑数 II & 剑指 49. 丑数 中的S2/S3,/S5
序列 - 质数
x = P0/P1/P2...
是 质数序列primes中的 质数
- 指针
ptr = p0/p1/p2
… 分别指向 序列 SP0/SP1/SP2… 中 未曾用过的 最小 值val
=s[ptr(p0/p1/p2)...]
*x(P0/P1/P2...)
- 注意 最小值
val
=s[ptr(p0/p1/p2)...]
*x(P0/P1/P2...)
,不只是 单独的s[ptr(p0/p1/p2)...]
,还要 乘上 所在序列SP0/SP1/SP2
… 对应的质数x = P0/P1/P2...
2. 代码注意事项:
-
从heap 弹出一个元素 后,肯定 也要 加入一个元素:
- 每次 从堆中 取出 一个元素
auto t = heap.top(); heap.pop();
, 这个元素(当前元素) 来自 序列SP0/SP1/SP2… 中某个序列,取出 这个元素后, 这个元素 可能放进 也可能不放进 丑数序列s中, 但 取出这个元素后肯定
要进行的 操作就是 将这个元素
所属序列 的 这个元素后面一个 元素
加入 堆中进行排序
,即heap.push({s[ptr + 1] * x, ptr + 1});
。
- 每次 从堆中 取出 一个元素
-
再回来看 这个元素 什么时候才能 加入 丑数序列 s 呢?答案:
if (val != s[idx - 1]) s[idx ++ ] = val;
- 如果 这个元素 等于 上一个生成的丑数 s[idx - 1]的话, 就不能加入丑数序列 s了
- 如果 不等于 s[idx - 1]的话, 就 可以加入丑数序列 s, 同时 将丑数下标 idx + 1.(注意是在 这个时候
idx ++
,而不是
在for循环中的条件
那里加 )
-
if (val != s[idx - 1]) s[idx ++ ] = val;
和heap.push({s[ptr + 1] * x, ptr + 1});
代码不能互换顺序。- 如果 互换, 很可能发生 当前 val 值还没 赋给丑数s[idx], 就直接 heap.push 就用到
s[idx]
(s[ptr + 1]的 ptr + 1 可能等于idx)了 - 举例: s[0]=1, 还没 进行赋值 s[1]=2 就直接用 heap.push({s[0+1]}) ,就用到丑数s[1]了,还没生成 就用了,显然不对。
- 如果 互换, 很可能发生 当前 val 值还没 赋给丑数s[idx], 就直接 heap.push 就用到
for (int idx = 1; idx <= n - 1; ) { // idx表示 当前生成丑数的下标. 注意 此处无 idx ++
auto t = heap.top(); heap.pop(); // 弹出 当前 最小值
auto val = t.first, ptr = t.second, x = val / s[ptr]; // 两者 推 第三个 信息
if (val != s[idx - 1]) s[idx ++ ] = val; // 不等于上一个丑数 时, 才 idx ++, 不是在for循环处 ++
heap.push({s[ptr + 1] * x, ptr + 1}); // 弹出一个元素 就要 加上一个元素
}
3. 复杂度分析:
- 时间复杂度:O(
max(nlogm, mlogm)
), 空间复杂度:O(n + m
)- 建堆: 时间O(
mlogm
), 空间O(m
) - 生成丑数序列 时间 O(
nlogm
),丑数序列 占用空间 O(n
)
- 建堆: 时间O(
4.详细注释版 代码:
// 时间复杂度:O( max(nlogm, mlogm) ), 空间复杂度:O(n + m)
// lc 264.丑数 II 的 质数2,3,5 对应序列 S2,S3,S5 对应指针 i,j,k 变成了
// --- 本题的 质数x = P0/P1/P2... 对应序列 SP0, SP1, SP2... 对应指针ptr = p0/p1/p2...
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) { // 假设 primes.size() = m
vector<int> s(n); // 空间O(n)
s[0] = 1; // idx表示 当前生成丑数的下标, 第1个丑数 是 s[0] = 1
// t.first 存 val = s[p0/p1/p2...] * P0/P1/P2... ,
// t.second 存 指向 序列SP0/SP1/SP2... 的 指针ptr = p0/p1/p2...
// 通过 val / s[p0/p1/p2...] = x(质数 P0/P1/P2...), 即
// x = t.first / s[t.second], 可知用的质数 x是 P0/P1/P2...中哪一个
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> heap;
// 初始化建堆, 假设 primes.size() = m, 存入 m 个元素, 根据 元素的 val值排序
// (s[0]初始化为 1) 存入 s[0]*P0, s[0]*P1, s[0]*P2...和对应指针 p0,p1,p2...(初始为0)
for (int x: primes) heap.push({s[0] * x, 0}); // 建堆 时间O(mlogm), 空间O(m)
for (int idx = 1; idx <= n - 1; ) { // idx表示 当前生成丑数的下标. 时间复杂度 O(nlogm)
auto t = heap.top(); heap.pop(); // 时间复杂度 O(1)
// 从heap 弹出一个元素 后,肯定 也要 加入一个元素:
// 每次 从堆中 取出 一个元素, 这个元素(当前元素) 来自 序列SP0/SP1/SP2... 中某个序列,
// 取出 这个元素后, 这个元素 可能放进 也可能不放进 丑数序列s中, 但 取出这个元素后 肯定
// 要进行的 操作就是 将 这个元素 所属序列 的 这个元素 后面一个 元素 加入 堆中进行排序.
auto val = t.first, ptr = t.second, x = val / s[ptr];
// 再回来看 这个元素 什么时候才能 加入 丑数序列 s 呢?
// --- 如果 这个元素 等于 上一个生成的丑数 s[idx - 1]的话, 就不能加入丑数序列 s了,
// --- 如果 不等于 s[idx - 1]的话, 就 可以加入丑数序列 s, 同时 将丑数下标 idx ++.
// 不同序列SP0, SP1, SP2... 相同元素 不重复 放入, 直接从 heap里面 pop掉, 不放入丑数序列 s
if (val != s[idx - 1]) s[idx ++ ] = val; // 不等于上一个丑数 时, idx才 ++, 不是在for循环处 ++
// 这一行 代码 与 下一行 代码不能 换顺序, 原因是
// 如果 互换, 很可能发生 当前 val 值还没 赋给丑数s[idx],
// --- 就直接 heap.push 就用到s[idx](s[ptr + 1]的 ptr + 1 可能等于idx)了
// 举例 s[0]=1, 还没 进行赋值 s[1]=2 就直接用 heap.push({s[0+1]})了
// 每次从 某一序列 SP0/SP1/SP2... 取出 指针ptr(p0/p1/p2...) 对应的 序列当前元素后,
// 将 该序列 该当前元素 的 后一个元素 加入堆中, 该元素对应指针ptr 向后移动一位 ptr + 1,
// ptr + 1 指向的就是后一元素, 将后一元素对应的 val = s[ptr + 1] * x 放入 堆中进行排序
heap.push({s[ptr + 1] * x, ptr + 1}); // 时间复杂度 O(logm)
}
return s[n - 1];
}
};
5. 简要注释版 代码:
// 时间复杂度:O( max(nlogm, mlogm) ), 空间复杂度:O(n + m)
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) { // 假设 primes.size() = m
vector<int> s(n); // 空间O(n)
s[0] = 1; // idx表示 当前生成丑数的下标, 第1个丑数 是 s[0] = 1
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> heap;
for (int x: primes) heap.push({s[0] * x, 0});
for (int idx = 1; idx <= n - 1; ) { // idx表示 当前生成丑数的下标. 注意 此处无 idx ++
auto t = heap.top(); heap.pop(); // 弹出 当前 最小值
auto val = t.first, ptr = t.second, x = val / s[ptr]; // 两者 推 第三个 信息
if (val != s[idx - 1]) s[idx ++ ] = val; // 不等于上一个丑数 时, 才 idx ++, 不是在for循环处 ++
heap.push({s[ptr + 1] * x, ptr + 1}); // 弹出一个元素 就要 加上一个元素
}
return s[n - 1];
}
};