-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path313.cpp
69 lines (68 loc) · 1.69 KB
/
313.cpp
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// better_priority_queue.cpp
class Solution {
struct ugly {
int base;
int index;
int sum;
bool operator()(ugly &a, ugly &b) { return a.sum > b.sum; }
};
public:
int nthSuperUglyNumber(int n, vector<int> &primes) {
priority_queue<ugly, vector<ugly>, ugly> pq;
vector<int> res(n, 1);
for (int i = 0; i < primes.size(); ++i)
pq.push(ugly{primes[i], 0, primes[i]});
for (int i = 1; i < n; ++i) {
ugly u = pq.top();
pq.pop();
if (u.sum <= res[i - 1])
--i;
else
res[i] = u.sum;
pq.push(ugly{u.base, ++u.index, u.base * res[u.index]});
}
return res[n - 1];
}
};
// priority_queue.cpp
class Solution2 {
public:
int nthSuperUglyNumber(int n, vector<int> &primes) {
priority_queue<long long int, vector<long long int>, greater<int>> pq;
pq.push(1);
long long int last = -1, temp;
while (n) {
long long int cur = pq.top();
pq.pop();
if (last != cur) {
last = cur;
--n;
for (int num : primes)
if ((temp = num * cur) <= (long long int)0x7fffffff)
pq.push(temp);
}
}
return last;
}
};
// usingVector.cpp
class Solution3 {
public:
int nthSuperUglyNumber(int n, vector<int> &primes) {
vector<int> index(primes.size(), 0), cache(primes), res(n, 1);
for (int i = 1; i < n; ++i) {
int minVal = 0x7fffffff, offset;
for (int j = 0; j < primes.size(); ++j)
if (cache[j] < minVal) {
minVal = cache[j];
offset = j;
}
if (minVal <= res[i - 1])
--i;
else
res[i] = minVal;
cache[offset] = res[index[offset]++] * primes[offset];
}
return res[n - 1];
}
};