What is the key idea behind generating super ugly numbers?

The key idea is using state transition dynamic programming where each number is derived by multiplying previous numbers by allowed primes and selecting the minimal next candidate.

Can duplicates occur in the sequence of super ugly numbers?

Yes, duplicates can occur if multiple primes multiply to the same candidate number; you must advance all corresponding pointers to avoid repeating numbers.

What should I initialize as the first super ugly number?

The first super ugly number is always 1, representing the base of the sequence with no prime factors.

How does pointer management improve efficiency?

Maintaining a pointer for each prime ensures you only multiply each prime with the smallest unused dp value, avoiding redundant calculations and reducing overall complexity.

Why is this problem considered a state transition dynamic programming pattern?

Because each super ugly number depends on previous numbers and pointers, forming a deterministic state that transitions to the next number based on minimal candidate selection across primes.

#313

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

超级丑数

超级丑数是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。给你一个整数 n 和一个整数数组 primes ，返回第 n 个超级丑数。题目数据保证第 n 个超级丑数在 32-bit 带符号整数范围内。示例 1：输入： n = 12, primes = [2,7,13…

数组数学动态规划

题目描述

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 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 中的所有值都 互不相同 ，且按 递增顺序 排列

lightbulb

解题思路

方法一：优先队列（小根堆）

我们用一个优先队列（小根堆）维护所有可能的超级丑数，初始时将 $1$ 放入队列中。

每次从队列中取出最小的超级丑数 $x$ ，将 $x$ 乘以数组 primes 中的每个数，将乘积放入队列中，然后重复上述操作 $n$ 次即可得到第 $n$ 个超级丑数。

由于题目保证第 $n$ 个超级丑数在 $32$ 位带符号整数范围内，因此，我们将乘积放入队列之前，可以先判断乘积是否超过 $2^{31} - 1$ ，如果超过，则不需要将乘积放入队列中。另外，可以使用欧拉筛优化。

时间复杂度 $O(n \times m \times \log (n \times m))$ ，空间复杂度 $O(n \times m)$ 。其中 $m$ 和 $n$ 分别为数组 primes 的长度和给定的整数 $n$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        q = [1]
        x = 0
        mx = (1 << 31) - 1
        for _ in range(n):
            x = heappop(q)
            for k in primes:
                if x <= mx // k:
                    heappush(q, k * x)
                if x % k == 0:
                    break
        return x

speed

复杂度分析

指标	值
时间	complexity is O(n * k) where n is the target index and k is the number of primes, since each step examines k candidates. Space complexity is O(n + k) to store the dp array and pointers, which is efficient for n up to 10^5 and primes up to 100.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks about efficiency beyond brute force multiplication
question_mark
Mentions handling large n with multiple primes
question_mark
Checks understanding of state transition dynamic programming

warning

常见陷阱

外企场景

error
Failing to initialize dp[0] as 1
error
Forgetting to advance multiple pointers when duplicate minimum occurs
error
Using naive brute-force multiplication, leading to timeouts for large n

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the nth ugly number with fixed primes [2,3,5] instead of a given array
arrow_right_alt
Find all super ugly numbers less than a given limit instead of nth number
arrow_right_alt
Count the number of super ugly numbers within a range [L, R]

help

常见问题

外企场景

继续练习

#368 最大整除子集 #396 旋转函数 #486 预测赢家