Super Ugly Number

任何一个ugly number都是由primes[] 里边的数字相乘得到。
如果我们用当前的ugly number 乘以 所有primes，放到priority queue 里边去，下次拿出来的就是下一个值。但是这中间会有重复。而且会产生很多不必要的值，因为小的primes*当前ugly 可能远小于大的primes*当前ugly。因此会产生memory limit exceeded

Memory Limit Exceeded

  public int nthSuperUglyNumber(int n, int[] primes) {  
     if(primes.length == 0) return 0;  
     PriorityQueue<Long> pq = new PriorityQueue<>();  
     pq.offer(1l);  
     while(n-->1){  
       long min = pq.poll();  
       while(!pq.isEmpty() && min == pq.peek()) pq.poll();  
       for(int i = 0 ; i < primes.length; i++)  
         if(min*primes[i] > min)  
           pq.offer(min*primes[i]);  
     }  
     return pq.poll().intValue();  
   }  

Ugly Number II 的 HINT：（primes={2,3,5}）

1. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
2. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.

因为An ugly number must be multiplied by任意一个primes里的值。因此对于下一个ugly number而言一定是一个之前的某个ugly number ✖️ primes[i]

因此要记录之前的ugly list 以及每个primes对应哪儿个ugly number

 public int nthSuperUglyNumber(int n, int[] primes) {  
     if(primes.length == 0) return 0;  
     int[] index = new int[primes.length];  
     int[] ans = new int [n+1];  
     ans[0] = 1;  
     for(int i = 1; i < n; i++){  
       int min = Integer.MAX_VALUE;  
       for(int j = 0; j < primes.length; j++){  
         min = Math.min(min, primes[j]*ans[index[j]]);  
       }  
       ans[i] = min;  
       for(int j = 0; j < primes.length; j++){  
         if(primes[j]*ans[index[j]] == min){  
           index[j]++;  
         }  
       }  
     }  
     return ans[n-1];  
   }