暴力法

  1. class Solution {
  2. public:
  3.     int nthSuperUglyNumber(int n, vector<int>& primes) {
  4.         set<long long> nums;
  5.         int count = 1;
  6.         nums.insert(1);
  7.         auto it = nums.begin();
  8.         for (; count < n; ++count, ++it) {
  9.             for (auto p : primes)
  10.                 nums.insert(*it * p);
  11.         }
  12.         return *it;
  13.     }
  14. };

时间复杂度在 313.超级丑数 2021-08-09 - 图1
空间复杂度 313.超级丑数 2021-08-09 - 图2

动态规划

  1. class Solution {
  2. public:
  3.     int nthSuperUglyNumber(int n, vector<int> &primes) {
  4.         vector<int> next(primes.size(), 0);
  5.         vector<int> dp(n);
  6.         dp[0] = 1;
  7.         for (int i = 1; i < n; ++i) {
  8.             int minum = INT32_MAX;
  9.             for (int j = 0; j < primes.size(); ++j)
  10.                 minum = min(dp[next[j]] * primes[j], minum);
  11.             for (int j = 0; j < primes.size(); ++j)
  12.                 if (minum == dp[next[j]] * primes[j])
  13.                     ++next[j];
  14.             dp[i] = minum;
  15.         }
  16.         return dp[n - 1];
  17.     }
  18. };

时间复杂度 313.超级丑数 2021-08-09 - 图3
空间复杂度 313.超级丑数 2021-08-09 - 图4