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 位有符号整数表示。

自建示例

由两个指定质数生成序列:

输入:n = 6,primes = [3, 5]
输出:25
解释:前六个超级丑数为 1、3、5、9、15、25,因此第六项是 25。

第一项与质数集合无关:

输入: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++ 实现

class Solution {
public:
    int nthSuperUglyNumber(
        int n, std::vector<int>& primes) {
        int primeCount = static_cast<int>(primes.size());
        std::vector<int> index(primeCount, 0);
        std::vector<long long> 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<int>(ugly[n - 1]);
    }
};

代码分析

每个质数对应一路已经有序的候选流,取各路头部最小值等价于多路归并;所有相等头部同步前进实现去重。n == 1 时循环不会执行,直接返回初始化的 1。每生成一项扫描一次质数数组,时间复杂度为 O(n * p)``(``p 为质数个数),空间复杂度为 O(n + p);内部用 long long 计算乘积后再按题目保证转回 int。