本文主要是介绍LeetCode *** 313. Super Ugly Number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
Write a program to find the n th super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
分析：
感觉自己数学能力确实还是不行。此题可以用pre*primes来归纳。只是这里的pre对于不同的primes都不同。
这道题的突破点在于每个数都总是之前某个数*一个质数。由于质数的列表我们已经找到，只需要建立“之前某个数”的表即可。
对于同样一串数字而言，乘不同的质数得到的结果自然是不一样的，那么我们只需要对每个质数建立一个属于自己的乘数列表即可。而该乘数列表自然就是我们一步一步得到的丑数数组。
在质数p1,p2,p3...pn分别乘自己的pre1,pre2,pre3...pren中，pi*prei最小，那么再将pi*prei赋给当前ugly[n]之后，pi的prei需要向前移一步。
代码：
class Solution {
public:int nthSuperUglyNumber(int n, vector<int>& primes) {vector<int> res(n,INT_MAX),index(primes.size(),0);res[0]=1;int size=primes.size();for(int i=1;i<n;++i){for(int j=0;j<size;++j)res[i]=min(res[i],res[index[j]]*primes[j]);for(int j=0;j<size;++j)index[j]+=(res[i]==res[index[j]]*primes[j]);}return res[n-1];}
};这篇关于LeetCode *** 313. Super Ugly Number的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
