leetcode 313. Super Ugly Number

Seawolf

1. Write a program to find the nth super ugly number.
   
2. 
   
3. Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.
   
4. 
   
5. Example:
   
6. 
   
7. Input: n = 12, primes = [2,7,13,19]
   
8. Output: 32
   
9. Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12
   
10.              super ugly numbers given primes = [2,7,13,19] of size 4.
    
11. Note:
    
12. 
    
13. 1 is a super ugly number for any given primes.
    
14. The given numbers in primes are in ascending order.
    
15. 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
    
16. The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

复制代码

1. class Solution {
   
2.     public int nthSuperUglyNumber(int n, int[] primes) {
   
3.         int[] arr = new int [n+1];
   
4.         arr[1] = 1;
   
5.         HashMap <Integer, Integer> map = new HashMap<>();
   
6.         
   
7.         for(int i = 0; i< primes.length ; i++){
   
8.             map.put(primes[i], 1);
   
9.         }
   
10.         for(int i = 2; i <= n ; i++){
    
11.             
    
12.             int min = Integer.MAX_VALUE;
    
13.             
    
14.             for(Integer key : map.keySet()){
    
15.                
    
16.                 if(key * arr[map.get(key)] < min){
    
17.                     min = key * arr[map.get(key)];
    
18.                 }
    
19.                
    
20.             }
    
21.             for(Integer key : map.keySet()){
    
22.                
    
23.                 if(key * arr[map.get(key)] == min){
    
24.                     map.put(key, map.get(key)+1);
    
25.                 }
    
26.                
    
27.             }
    
28.             arr[i] = min;
    
29.         }
    
30.         return arr[n];
    
31.     }
    
32. }

复制代码

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

复制代码