313. Super Ugly Number ---M

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.

Example:

Input: n = 12, primes = [2,7,13,19]
Output: 32 
Explanation: [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 is a super ugly number for any given primes.
• The given numbers in primes are in ascending order.
• 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
• The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

A:

动态规划，ugly number一定是由一个较小的ugly number乘以2，3或5得到的。

先开一个数组记录所有的ugly number。

然后开一个变量数组A，一开始都是零，指向数组的第0位。    A[i]是ugly number的index，

A[i] * primes[i] > current ugly number

每一次取Min(A[i] * primes[i])，找到这个数之后，对应的A[i]加一，指向数组的下一位。

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> list{1};
        int m = primes.size();
        vector<int> Index(m, 0);
        while(list.size()<n){
            vector<int> V;
            int last = list.back();
            for(int i =0;i<m; i++){ // for each prime number
                while(list[Index[i]]*primes[i] <= last){
                    Index[i]++;
                }
                V.push_back(list[Index[i]]*primes[i]);
            }
            list.push_back(*min_element(V.begin(), V.end()));
        }
        return list[n-1];
    }
};

Mistakes:
第二遍的时候，
1：  在while中，以为不会有相等的。  因此只用了 < ，这样是不对的。
2：  如果res 改成list,  会超时

****************用 min-heap 会超时****************

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        Queue<Integer> minHeap = new PriorityQueue(n*primes.length,new Comparator<Integer>(){
            public int compare(Integer a, Integer b){
                return a-b;
            } 
        });
        minHeap.add(1);
        Set<Integer> set = new HashSet();
        int lastVal = 0, count = 0;
        while(count < n){
            int val = minHeap.poll();
            for(int i =0;i<primes.length; i++)
                if(val <= Integer.MAX_VALUE / primes[i] && !set.contains(val*primes[i])){
                    minHeap.add(val * primes[i]);
                    set.add(val* primes[i]);
                }
            count ++;
            lastVal = val;
        }
        return lastVal;
    }
}