[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）注意重合的情况，也就是说不一定只有一个位置产生最小值，所有产生最小值的位置都要向后移动

三、代码实现

 1 class Solution {
 2 public:
 3     int nthSuperUglyNumber(int n, vector<int>& primes) {
 4         if (n < 1)return 0;
 5         vector<int> dp(n, 0);
 6         int m = primes.size();
 7         if (!m)return 1;
 8         vector<int> idx(m, 0);
 9         dp[0] = 1;
10         int min_pos;
11         for (int i = 1; i < n; ++i) {
12             dp[i] = dp[idx[0]] * primes[0];
13             min_pos = 0;
14             for (int j = 1; j < m; ++j) {
15                 if (dp[i] > dp[idx[j]] * primes[j]) {
16                     dp[i] = dp[idx[j]] * primes[j];
17                 }
18             }
19             for (int j = 0; j < m; ++j) {
20                 if (dp[i] == dp[idx[j]] * primes[j])//有的会有重合的部分，比如2*7==7*2，所有的位置都要向后移动
21                     ++idx[j];
22             }
23         }
24         return dp[n - 1];
25     }
26 };

[Leetcode] 第313题 超级丑数

[Leetcode] 第313题超级丑数