0313. Super Ugly Number
=======================
题目信息
--------
:题号: 0313
:难度: Medium
:主题: 正整数序列、指定质因子、第 n 项、结果去重
:原题: `LeetCode 0313 `_
:重点: ``1`` 是第一项、所有质因子必须来自给定集合、相同数值只占一个序列位置
题目重述
--------
超级丑数是所有质因子都属于数组 ``primes`` 的正整数,数值 ``1`` 也被定义为超级丑数。给定正整数 ``n`` 和严格递增、互不相同的质数数组 ``primes``,返回按数值从小到大排列的第 ``n`` 个超级丑数。
``n`` 位于 ``[1, 10^5]``,``primes`` 的长度位于 ``[1, 100]``,每个质数位于 ``[2, 1000]``。不同质因子乘积可能生成同一个数,该数在序列中只能出现一次。题目保证第 ``n`` 个超级丑数可以由 32 位有符号整数表示。
自建示例
--------
由两个指定质数生成序列:
.. code-block:: text
输入:n = 6,primes = [3, 5]
输出:25
解释:前六个超级丑数为 1、3、5、9、15、25,因此第六项是 25。
第一项与质数集合无关:
.. code-block:: text
输入:n = 1,primes = [7, 13]
输出:1
解释:按照题目定义,1 始终是超级丑数序列的第一项。
多路合并所有可生成的候选
--------------------------
超级丑数序列从 ``1`` 开始。若已经得到排好序的前缀 ``ugly``,下一项必然可以写成某个已出现的超级丑数乘以一个 ``primes`` 中的质数。为每个质数维护一个指针 ``index[j]``,表示当前还没有使用的候选 ``ugly[index[j]] * primes[j]``;所有候选的最小值就是下一个超级丑数。
一个数可能由多条路生成,例如质数集合包含 2 和 3 时,6 既可能来自 ``2 * 3``,也可能来自 ``3 * 2``。选出最小候选后,必须把所有等于该值的指针一起前进,否则同一个数会在序列中重复出现,后续第 ``n`` 项也会错位。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int nthSuperUglyNumber(
int n, std::vector& primes) {
int primeCount = static_cast(primes.size());
std::vector index(primeCount, 0);
std::vector ugly(n, 0);
ugly[0] = 1;
for (int i = 1; i < n; ++i) {
long long next = LLONG_MAX;
for (int j = 0; j < primeCount; ++j) {
next = std::min(
next, ugly[index[j]] * primes[j]);
}
ugly[i] = next;
for (int j = 0; j < primeCount; ++j) {
if (ugly[index[j]] * primes[j] == next) {
++index[j];
}
}
}
return static_cast(ugly[n - 1]);
}
};
代码分析
--------
每个质数对应一路已经有序的候选流,取各路头部最小值等价于多路归并;所有相等头部同步前进实现去重。``n == 1`` 时循环不会执行,直接返回初始化的 1。每生成一项扫描一次质数数组,时间复杂度为 ``O(n * p)``(``p`` 为质数个数),空间复杂度为 ``O(n + p)``;内部用 ``long long`` 计算乘积后再按题目保证转回 ``int``。