[Leetcode] 第313题 超级丑数

一、题目描述

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

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

示例:

输入: 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 是任何给定 primes 的超级丑数。
• 给定 primes 中的数字以升序排列。
• 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
• 第 n 个超级丑数确保在 32 位有符整数范围内。

二、题目分析

1）参考丑数II中用的方法，不同的是丑数II中只有2,3,5三个质因数，而现在的质因数个数不一定
2）丑数II中使用pos2,pos3,pos5分别代表当前应该乘以2,3,5的位置，那么现在用idx[i]来代表当前应该乘以primes[i]的位置
3）同样的，dp[i]代表第i-1个丑数
4）那么dp[i]=min{dp[idx[j]]*primes[j]},0<=j<idx.size(),也就是选择当前位置的丑数和应该乘以的质因数的最小值
5）注意重合的情况，也就是说不一定只有一个位置产生最小值，所有产生最小值的位置都要向后移动

三、代码实现

 class Solution {

 public:

     int nthSuperUglyNumber(int n, vector<int>& primes) {

         if (n < )return ;

         vector<int> dp(n, );

         int m = primes.size();

         if (!m)return ;

         vector<int> idx(m, );

         dp[] = ;

         int min_pos;

         for (int i = ; i < n; ++i) {

             dp[i] = dp[idx[]] * primes[];

             min_pos = ;

             for (int j = ; j < m; ++j) {

                 if (dp[i] > dp[idx[j]] * primes[j]) {

                     dp[i] = dp[idx[j]] * primes[j];

                 }

             }

             for (int j = ; j < m; ++j) {

                 if (dp[i] == dp[idx[j]] * primes[j])//有的会有重合的部分，比如2*7==7*2，所有的位置都要向后移动

                     ++idx[j];

             }

         }

         return dp[n - ];

     }

 };