leetcode SuperUglyNumber
z
 2019-04-09 10:36:27   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.HashMap;

public class SuperUglyNumber {
  /**
   * 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.
   */
  public int nthSuperUglyNumber(int n, int[] primes) {
    HashMap<Integer, Integer> idxs = new HashMap<>();
    for (int i: primes){
      idxs.put(i, 0);
    }
    int dp[] = new int[n];
    for (int i=0; i<n; i++){
      int min = Integer.MAX_VALUE;
//      int minPrime = 0;
      for (int idx : idxs.keySet()){
        if (min > dp[idx] * idx){
          min = dp[idx]*idx;
//          minPrime = idx;
        }
      }
      dp[i] = min;
//      idxs.put(minPrime, idxs.get(minPrime)+1);
      for (int idx: idxs.keySet()){
        if (dp[i] == idx*dp[idxs.get(idx)]){
          idxs.put(idx, idxs.get(idx)+1);
        }
      }
    }
    return dp[primes.length-1];
  }
}