Sponsored
Sponsored
This approach uses a min-heap to efficiently find the kth smallest fraction. By iterating through each pair of elements (i, j) in the array where i < j, we can calculate the fraction arr[i]/arr[j] and push it into the heap. The heap is then used to retrieve the k-th smallest element efficiently.
Time Complexity: O(n^2 log(n^2))
Space Complexity: O(n^2)
1#include <vector>
2#include <queue>
3#include <utility>
4
5using namespace std;
6
7vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
8 int n = arr.size();
9 auto cmp = [&](pair<int, int>& a, pair<int, int>& b) {
10 return arr[a.first] * arr[b.second] > arr[b.first] * arr[a.second];
11 };
12 priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
13 for (int i = 0; i < n; ++i) pq.emplace(i, n - 1);
14 pair<int, int> result;
15 while (k--) {
16 result = pq.top();
17 pq.pop();
18 if (result.second - 1 > result.first) {
19 pq.emplace(result.first, result.second - 1);
20 }
21 }
22 return {arr[result.first], arr[result.second]};
23}This C++ code uses a priority queue (min-heap) to maintain the smallest fractions. The priority queue orders elements based on the current fraction value represented by elements in the array. We then extract the smallest element k times to find and return the k-th smallest fraction.
This approach uses binary search on the value of fractions. By implementing a search over the potential range of fraction values, the algorithm counts how many fractions are less than a given mid-point, narrowing down to the k-th one by manipulating the bounds of the potential fraction values. A two-pointer technique helps count the fractions efficiently.
Time Complexity: O(n log(max_fraction))
Space Complexity: O(1)
1
public class Solution {
public int[] KthSmallestPrimeFraction(int[] arr, int k) {
double lo = 0.0, hi = 1.0;
while (hi - lo > 1e-9) {
double mid = (lo + hi) / 2.0;
int count = 0;
int p = 0, q = 1;
double maxFraction = 0.0;
int i = 0;
for (int j = 1; j < arr.Length; j++) {
while (i < j && arr[i] < arr[j] * mid) i++;
count += i;
if (i > 0) {
double fraction = (double)arr[i - 1] / arr[j];
if (fraction > maxFraction) {
maxFraction = fraction;
p = arr[i - 1];
q = arr[j];
}
}
}
if (count < k) lo = mid;
else {
hi = mid;
result[0] = p;
result[1] = q;
}
}
return result;
}
}The C# implementation uses binary search and a two-pointer method to count and track fractions. Adjusting the fraction value bounds is key to finding the k-th smallest fraction.