leetcode 313. 超级丑数

题目链接 https://leetcode-cn.com/problems/super-ugly-number/submissions/

题目描述

1. 编写一段程序来查找第 n 个超级丑数。

   超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。

2. 输入: 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] 。

解题思路

1. 类似于丑数，扩展的多指针法
2. 下一个丑数一定是之前的丑数乘上primes 所获得的最小值。
3. 在计算下一个丑数的时候，我们不需要从头计算，通过index数组，将primes中每个因数所乘的之前丑数的索引保存下来。计算min（primes[i] * res[index[i]]）即可

代码

1. python

   class Solution:
       def nthSuperUglyNumber(self, n, primes):
           res = [1]
           N = len(primes)
           index = [0] * N
           while len(res) != n:
               _min = float("inf")
               for i in range(N):
                   _min = min(_min, primes[i] * res[index[i]])
               for i in range(N):
                   index[i] += _min == primes[i] * res[index[i]]
               res.append(_min)
           return res[-1]