313. Super Ugly Number java solutions

Write a program to find the nth 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.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

 1 public class Solution {
 2     public int nthSuperUglyNumber(int n, int[] primes) {
 3         if(n < 1) return 0;
 4         int len = primes.length;
 5         int[] dp = new int[n];
 6         int[] index = new int[len];
 7         dp[0] = 1;
 8         for(int i = 1; i < n; i++){
 9             int min = Integer.MAX_VALUE;
10             for(int j = 0; j < primes.length; j++){
11                 min = Math.min(min,dp[index[j]]*primes[j]);
12             }
13             dp[i] = min;
14             for(int k = 0; k < len; k++){
15                 if(dp[i]%primes[k] == 0)
16                     index[k]++;
17             }
18         }
19         return dp[n-1];
20     }
21 }

超级丑数。跟丑数II很类似，只不过这次primes从2, 3, 5变成了一个size k的list。方法应该有几种，一种是维护一个size K的min-oriented heap，heap里是k个queue，和Ugly Number II的方法一样，取最小的那一个，然后更新其他Queue里的元素，n--，最后n = 1时循环结束。另外一种是类似dynamic programming的方法，主要参考了larrywant2014大神的代码。维护一个index数组，维护一个dp数组。每次遍历更新的转移方程非常巧妙，min = dp[[index[j]]] * primes[j]。之后再便利一次primes来update每个数在index[]中的使用次数。

Time Complexity - O(nk)， Space Complexity - O(n + k).

参考：

https://discuss.leetcode.com/topic/34841/java-three-methods-23ms-36-ms-58ms-with-heap-performance-explained

http://www.cnblogs.com/yrbbest/p/5062988.html