Given an integer array of size $n$ containing prime integers, it can form $n(n-1)/2$ fractions, we are required to find the $k$-th smallest prime fraction.
Intuition
We can use a priority queue to store prime integers, then we maintain the priority queue.
Approach1: Brute force
Complexity
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
class Compare {
public:
bool operator()(const vector<int>& a, const vector<int>& b){
return 1.0 * a[0] / a[1] < 1.0 * b[0] / b[1]; // the root is the biggest
}
};
public:
vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
priority_queue<vector<int>, vector<vector<int>>, Compare> pq;
int n = arr.size();
for (int r = 1; r <= k + 1; ++r) {
for (int i = 0; i < n; ++i) {
if (i + r >= n) break;
pq.push(vector<int>{arr[i], arr[i + r]});
if (pq.size() > k) {
pq.pop();
}
}
}
return pq.top();
}
};
|
Approach2: Simplification
Notice that Approach1 requires iterating over all fractions, can we reduce the time complexity?
The solution is by considering the relative order, if we write a matrix whose element a[i][j]=nums[i]/nums[j] (i<j), then we know that a[i][i+1]>...>a[n-1][n] since the array nums are increasing. So, the smallest fraction are in a[1][2], ..., a[n-1][n]. If we take the smallest fraction, and add its successive elements (same column, last row), then we can find the second smallest fraction and so on. This solution requires iterating over $\max(n, k)$ fractions and $O(n)$ spaces.
Complexity
- $$O(\max(n, k)\log n)$$
- $$O(n)$$
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
// (fraction, (i, j))
priority_queue<pair<double, pair<int, int>>> pq;
for (int i = 0; i < A.size(); ++i) {
pq.push({-1.0 * A[i] / A.back(), {i, A.size() - 1}});
}
while (--K) {
auto t = pq.top().second;
q.pop();
--t.second;
pq.push({-1.0 * A[t.first] / A[t.second], {t.first, t.second}});
}
return {A[pq.top().second.first], A[pq.top().second.second]};
}
};
|
Reference