BiruLyu
8/14/2017 - 9:34 PM

## 313. Super Ugly Number(Approach#1).java

``````public class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int len = primes.length;
int[] cnt = new int[len];
int[] res = new int[n];
Arrays.fill(res, Integer.MAX_VALUE);
res[0] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < len; j++) {
res[i] = Math.min(res[i], res[cnt[j]] * primes[j]);
}
for (int j = 0; j < len; j++) {
if (res[i] == res[cnt[j]] * primes[j]) {
cnt[j]++;
}
}
}
return res[n - 1];
}
}``````
``````public int nthSuperUglyNumberHeap(int n, int[] primes) {
int[] ugly = new int[n];

PriorityQueue<Num> pq = new PriorityQueue<>();
for (int i = 0; i < primes.length; i++) pq.add(new Num(primes[i], 1, primes[i]));
ugly[0] = 1;

for (int i = 1; i < n; i++) {
ugly[i] = pq.peek().val;
while (pq.peek().val == ugly[i]) {
Num nxt = pq.poll();
pq.add(new Num(nxt.p * ugly[nxt.idx], nxt.idx + 1, nxt.p));
}
}

return ugly[n - 1];
}

private class Num implements Comparable<Num> {
int val;
int idx;
int p;

public Num(int val, int idx, int p) {
this.val = val;
this.idx = idx;
this.p = p;
}

@Override
public int compareTo(Num that) {
return this.val - that.val;
}
}``````