一、题目

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes中。

给你一个整数 n和一个整数数组 primes，返回第 n个 超级丑数 。

题目数据保证第 n个 超级丑数 在 32-bit带符号整数范围内。

点击查看原题
难度级别： 中等

二、思路

1）动态规划

建立一个数组dp[i]代表第i个超级丑数的值，建立products[j]数组和points[k]数组，每次在products数组中找到最小值即当前遍历到的超级丑数，points[j]自增，products[j]中的新值为primes[j]*dp[``points[j]``]（为了防止数组中的值重复，每次都要遍历products中，看是否有重复数据，有就后移指针，并更新products对应位置的值）

三、代码

1）动态规划

  1. class Solution {
  2.     public int nthSuperUglyNumber(int n, int[] primes) {
  3.         int[] dp = new int[n + 1];
  4.         dp[1] = 1;
  5.         int[] points = new int[primes.length];
  6.         int[] products = new int[primes.length];
  7.         for (int i = 0; i < primes.length; i++) {
  8.             points[i] = 1;
  9.             products[i] = primes[i];
  10.         }
  11.         for (int i = 2; i <= n; i++) {
  12.             int minLoc = 0;
  13.             for (int j = 1; j < products.length; j++) {
  14.                 if (products[j] < products[minLoc]) {
  15.                     minLoc = j;
  16.                 }
  17.             }
  18.             dp[i] = products[minLoc];
  19.             for (int j = 0; j < products.length; j++) {
  20.                 if (dp[i] == products[j]) {
  21.                     points[j]++;
  22.                     products[j] = dp[points[j]] * primes[j];
  23.                 }
  24.             }
  25.         }
  26.         return dp[n];
  27.     }
  28. }

m为primes的长度，时间复杂度为O(n*m)，空间复杂度为O(n+2*m)