313. 超级丑数

题目描述

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

思路

和 264. 丑数 II 类似，利用动态规划维护一个当前质数数组对应的最小质因数数组，例如，对于 primes = [2, 7, 13, 19]，可以有：

设数组 ptr = [0, 0, 0, 0]，代表该质数数组能乘的数字在质因数数组中的位置。质因数数组初始状态为 ans = [1]。

维护一个 dp 数组，为 dp[i] = primes[i] * ans[ptr[i]]，它的最小值就是加入质因数数组的最新值。

如果遇到了最小值（可能有多个），对应的 ptr[i]++。

对于上面的例子

• 第一轮：dp = [2, 7, 13, 19] ptr = [1, 0, 0, 0] ans = [1, 2]
• 第二轮：dp = [4, 7, 13, 19] ptr = [2, 0, 0, 0] ans = [1, 2, 4]
• 第三轮：dp = [8, 7, 13, 19] ptr = [2, 1, 0, 0] ans = [1, 2, 4, 7]
• 第四轮：dp = [8, 14, 13, 19] ptr = [3, 1, 0, 0] ans = [1, 2, 4, 7, 8]
• 第五轮：dp = [14, 14, 13, 19] ptr = [4, 1, 1, 0] ans = [1, 2, 4, 7, 8, 13]
• 第六轮：dp = [14, 14, 26, 19] ptr = [5, 2, 1, 0] ans = [1, 2, 4, 7, 8, 13, 14]

依此类推。

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        l = len(primes)
        ans = [1] + [0 for _ in range(n-1)]
        ptr = [0 for _ in range(l)]
        for i in range(1, n):
            dp = [primes[j] * ans[ptr[j]] for j in range(l)]
            min_num = min(dp)
            ans[i] = min_num
            for j in range(l):
                if dp[j] == min_num:
                    ptr[j] += 1
        return ans[n-1]

想得太多